PERBANDINGAN ALGORITMA DIJKSTRA DAN ALGORITMA FLOYD-WARSHALL UNTUK MENYELESAIKAN SHORTEST PATH PROBLEM

Salah satu persoalan yang timbul dalam graf adalah bagaimana

menemukan lintasan terpendek (shortest path). Untuk menyelesaikan persoalan

ini, langkah pertama adalah memodelkan persoalan. Setelah itu, kita harus

menganalisis dengan membuat beberapa lintasan atau rute melalui beberapa

simpul yang total bobot atau jaraknya minimum. Lintasan tergantung pada hasil

yang optimal dan waktu komputasinya.

Ada 2 cara untuk mengatasi masalah ini. Pertama dengan menggunakan

Algoritma Dijkstra. Dan yang kedua dengan menggunakan algoritma

Floyd-Warshall. Cara kerja algoritma Dijkstra adalah dengan cara menandai

setiap simpul yang terpilih dengan permanen label sampai semua simpul

mendapat permanen label. Kemudian semua lintasan dibandingkan dan dicari

lintasan yang memiliki total bobot minimum. Sedangkan cara kerja algoritma

Floyd-Warshall adalah menandai setiap simpul berurutan dari simpul awal sampai

simpul tujuan. Kemudian pencarian lintasannya hanya bisa dari simpul awal

langsung ke simpul tujuan atau boleh melewati satu simpul lain yang sudah

ditandai untuk sampai ke simpul tujuan. Setelah itu dibandingkan dan dicari

lintasan yang memiliki total bobot minimum.

Kedua algoritma ini dibandingkan cara kerjanya sehingga kita bisa

menganalisa hasilnya untuk mendapatkan hasil yang optimal sesuai dengan yang

diharapkan.