Algoritma Dijkstra

Algoritme Dijkstra,, adalah sebuah algoritme rakus yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graf berarah dengan bobot-bobot garis yang bernilai nonnegatif, [ 0 , ∞ ) . Input algoritme ini adalah sebuah graf berarah yang berbobot G dan sebuah titik asal s dalam himpunan garis V . Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Biaya (cost) dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik s dan t dalam V , algoritme ini menghitung jarak terpendek dari s ke t .