Perbandingan Algoritma Dijkstra dan Floydwarshall dalam Pemilihan Rute Terpendek Jaringan Jalan (Studi Literatur)

Abstract

Kemacetan yang sering terjadi selama perjalanan, sering mengganggu kegiatan kita sehari-hari. Setiap manusia ingin sampai ke tujuan dengan tepat waktu. Tetapi, sering kali kemacetan menyebabkan keinginan manusia terganggu. Oleh karena itu, dibutuhkan suatu cara untuk menanggulangi gangguan tersebut. Untuk mencapai suatu tempat dengan waktu yang lebih cepat, kita akan mencari lintasan terpendek dari tempat asal ke tempat tujuan. Saat ini banyak sekali algortima-algoritma yang dapat digunakan untuk menyelesaikan persoalan penentuan lintasan terpendek (shortest path problem) dari suatu rute. Ada dua algortima yang cukup terkenal yang bisa digunakaan untuk menyelesaikan persoalan lintasan terpendek, yaitu Algoritma Dijkstra dan Algoritma Floyd-Warshall. Algoritma Dijkstra ini menggunakan prinsip greedy yang menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukkannya ke dalam himpunan solusi sedangan algoritma Floyd-Warshall menggunakan prinsip dinamis yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu. Beberapa analisa pun menunjukkan beberapa keuntungan dan kelemahan dari kedua algoritma tersebut.