Algoritma Dijkstra

Algoritma Dijkstra menemukan jalan terpendek dari satu vertex v0 sama simpul lain dalam

digraf. Ketika selesai, panjang jarak terpendek dari v0 ke v disimpan dalam vertex v, dan jalan terpendek dari v0 ke v dicatat dalam pointer belakang v dan yang lainnya simpul di sepanjang jalan itu.

Algoritma ini menggunakan antrian prioritas, menginisialisasi itu dengan semua simpul dan kemudian dequeueing satu simpul pada setiap iterasi.

Teori Graf

 Graf  (graph) adalah himpunan benda-benda yang disebut simpul(vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Graf trival (satu titik tampa sisi satu pun)

Jenis graf antara lain :

1. Berdasarkan ada tidaknya sisi ganda

    a. graf sederhana

    b. graf tidak sederhana

        1)graf ganda (multigraf)

        2)graf semu(pseudograf) adalah graf yang mengandung gelang (loop)

           graf sedrehana --> graf ganda

           graf ganda -x-> graf sederhana