Khazhar Blog

jika ada nilai negatif, algoritma dijkstra tidak membenarkannya. Disinilah masalahnya, padahal dapat ditemukan jalan yang lebih dekat menuju simpul yang paling dekat untuk mencapai tujuannya. Sehingga bisa dibilang Algortma Dijkstra tidak dapat mengatasi nilai negatif sebgai solusi terpendek untuk mencapai node dan membuat path yang diambil semakin banyak.

Ilustrasi kelemahan Algoritma Dijkstra,

Contoh Algoritma dijkstra :

void negativelyWeightedSSSP(int s, int[] dist)

{

for (v = 0; v <>

dist[v] = INFINITY;

Queue q = new Queue(n);

dist[s] = 0;

q.enqueue(s);

while (q.notEmpty())

{

v = q.dequeue();

for (each neighbor w of v)

if (dist[w] > dist[v] + weight[v, w]) // shorter path

{

dist[w] = dist[v] + weight[v, w];

if (! q.isInQueue(w))

q.enqueue(w);

}

}

}

Jika saya tidak salah mengartikan, Algoritma Dijkstra akan membuat (path) jalan yang lebih banyak dan mengambil waktu yang lebih bnyak dalm mencapai jalan tersingkat dalam membuat spanning tree karena ia tidak mendefinisikan nilai minus sebagai sebuah path dan harus melakukan trace-back berulang-ulang. Vice versa(sebaliknya),Bellman ford menggunakan nilai minus dalam mencapai jalan(path) tersingkat sehingga lebih sedikit melakukan trace-back. Tetapi Algortma Bellman Ford tidak lebih baik dari algorima Warshall. Dalam kasus lain, karena Algoritma DIjkstra sudah melakukan trace-back dan telah membandingkan dengan nilai path akhir dengan nilai-nilai sebelumnya maka Algoritma ini sudah bisa memastikan bahwa nilai akhir merupakan path terpendek yang diambil. Berbeda dengan Bellman Ford, nilai terakhir dari path memang benar path yang terpendek, tapi masalahnya adalah Algoritma ini tidak mengetahui mana simpul yang terakhir, sehingga ia harus memunculkan simpul yang tidak perlu untuk membentuk sebuah sirkuit dan melakukan trace-back kembali.

Untuk lebih mudah silahkan lihat gambar berikut, yang menunjukkan proses algoritma Bellman-Ford.

Banyak sekali pertanyaan tentang algoritma ini, sehigga disarankan kepada pembaca tidak langsung memngambil apa yang saya tangkap. Untuk lebih jelasnya silahkan kunjungi alamat ini : web Bellman Ford

Pertanyaan : Apa jalan minus yang diambil Algoritma Bellman Ford mempresentasikan keadaan yang sperti apa?