Sejarah 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 – seorang ilmuwan computer 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(OR). Implementasi algoritma dijkstra pada ilmu computer antara lain adalah pada link-state routing protocol, OSPF dan IS-IS.
Pada literatur tersebut, algoritma ini sering digambarkan sebagai sebuah algoritma yang 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]).
Properti algoritma Dijkstra:
1. Matriks ketetanggaan M[mij]
mij = bobot sisi (i, j)
mii = 0
mij = ∞, jika tidak ada sisi dari simpul i ke simpul j
2. Larik S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
3. Larik/tabel D = [di] yang dalam hal ini,
di = panjang lintasan dari simpul awal s ke simpul i
Algoritma Lintasan Terpendek Dijkstra (Mencari lintasan terpendek dari simpul a ke semua simpul lain).
Contoh program algoritma djikstra silakan unduh disini..
No comments:
Post a Comment