Algoritma Dijkstra

Sekilas Tentang Algoritma Dijkstra

Pada tahun 1959 sebuah tulisan sepanjang tiga halaman yang berjudul A Note on Two Problems in Connexion with Graphs diterbitkan pada jurnal  Numerische Mathematik. Pada tulisan ini, Edsger W. Dijkstra adalah seorang ilmuwan komputer berumur dua puluh sembilan tahun mengusulkan algoritma-algoritma untuk solusi dari dua masalah teoritis graf dasar : the minimum weight. Algoritma Dijkstra untuk masalah jalan terpendek adalah satu dari algoritma-algoritma paling ternama pada ilmu komputer dan sebuah algoritma paling popular pada oparasi pencarian. Implementasi algoritma dijkstra pada ilmu komputer antara lain adalah pada link-state routing protocol, OSPF dan IS-IS.
Pada literatur tersebut, algoritma ini sering digambarkan sebagai sebuah algoritma yang rakus / tamak. Contohnya, buku Algorithmics (Brassard and Bratley [1988, pp. 87-92] )mengulas ini pada bab tersebut dengan judul Greedy Algorithms. Encyclopedia of Operations Research and Management Science (Gass and Harris [1996, pp. 166-167]) menggambarkan algoritma ini sebagai sebuah "node labelling greedy algorithm " dan sebuah algoritma yang tamak digambarkan sebagai "a heuristic algorithm that at every step selects the best choice available at that step without regard to future consequences " (Gass and Harris [1996, p. 264]).

Definisi Algoritma Dijkstra

Pada dasarnya, algoritma ini merupakan salah satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif, dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing.
Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :
Untuk setiap simpul sumber(source) dalam graf, algortima ini akan mencari jalur dengan cost minimum antara simpul tersebut dengan simpul lainnya. Algoritma juga dapat digunakan untuk mencari total biaya (cost) dari lintasan terpendek yang dibentuk dari sebuah simpul ke sebuah simpul tujuan. Sebagai contoh, bila simpul pada graf merepresentasikan kota dan bobot sisi merepresentasikan jarak antara 2 kota yang mengapitnya, maka algoritma dijkstra dapat digunakan untuk mencari rute terpendek antara sebuah kota dengan kota lainnya.