Algoritma Dijkstra dalam Ilustrasi

Algoritma Dijsktra (diambil dari nama penemunya, Edsger Dijkstra) merupakan algoritma yang terkenal untuk menyelesaikan permasalahan lintasan terpendek (shotest-paths problems) pada suatu graf berbobot.

Algoritma ini mengemban strategi greedy, karena setiap langkah dalam prosesnya akan selalu memilih satu di antara sekian lintasan tunggal (single path) yang tersedia dengan biaya (cost) minimum; dimana biaya ini merupakan nilai yang bisa saja kosong, tunggal, ataupun akumulatif yang tergantung banyak sisi (edge) pembentuk lintasan dari titik awal ke titik akhir.

Dijkstra biasanya dipakai untuk menemukan solusi pencarian lintasan terpendek menggunakan satu buah simpul (vertex) sebagai sumber dan semua simpul lain dalam graf sebagai tujuannya (single-source shortest paths).

Pseudocode

Algorithm: Dijkstra(G, src)
Input: Graph G = (V, E) with edge weights and source vertex src.
    
    // dist: distance (jarak dari sumber ke simpul)
    // pred: predecessor (satu simpul sebelum)

    vertex set PQ                   // antrian prioritas

    for each vertex v in G do
       v.dist ← INFINITY
       add v to PQ
    src.dist ← 0 

    while PQ is not empty do
      v ← PQ.poll                  // ambil simpul dengan jarak terendah di PQ 
      for each neighbor u of v do
         w ← edge weight of (v, u)
         if w + v.dist < u.dist 
            u.dist ← v.dist + w    // ubah jarak u
            u.pred ← v             // ganti predecessor u

    return G

Contoh Kasus

Terdapat sebuah graf, terdiri atas 6 buah simpul yang masing-masing secara berturut diberi pelabelan huruf abjad 'A' sampai dengan 'F'. Keenamnya terkoneksi melalui beberapa sisi dengan variasi bobot (weight) yang dimilikinya. Algortima Dijkstra akan coba diterapkan untuk menemukan single-source shortest paths menggunakan verteks B sebagai sumber pencarian ini.

1. Inisialisasi

Berikan nilai tak hingga sebagai jarak (distance) setiap simpul.
Predecessor (satu simpul sebelum) setiap simpul sengaja tidak didefinisikan.
Isikan secara bertahap antrian berprioritas dengan satu per satu simpul.

Setelahnya khusus hanya untuk simpul C, atur kembali jaraknya, kali ini dengan nilai 0. Pengubahan jarak kedua kalinya untuk C ini dimaksudkan agar menjadi yang terkecail daripada yang lain, sehingga penelusuran dapat dimulai darinya.