Perbandingan Algoritma Dijkstra dan Floyd-Warshall Dalam Mencari Rute Terpendek Jaringan Jalan
| Main Author: | Sitanggang, Sondang |
|---|---|
| Other Authors: | Aswad, Yusandy |
| Format: | Student Papers |
| Bahasa: | ind |
| Subjects: | |
| Online Access: |
http://repository.usu.ac.id/handle/123456789/28846 |
Daftar Isi:
- 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.
- 050404105