ANALISIS KINERJA ALGORITMA DIJKSTRA DAN BELLMAN-FORD DALAM PENYELESAIAN MASALAH LINTASAN TERPENDEK
(Studi Kasus: Sistem Transportasi di Kota Bengkulu)
Total View This Week0
Total View This Week0
Institusion
Universitas Bengkulu
Author
Primadona, Hengki
Fanani, Haryo Widodo
Mudin, Simanihuruk
Fanani, Haryo Widodo
Mudin, Simanihuruk
Subject
QA Mathematics
Datestamp
2013-10-17 21:18:51
Abstract :
Skripsi ini membahas tentang analisis kinerja algoritma Dijkstra dan Bellman-Ford dengan studi kasus jalur lintasan angkutan umum di kota Bengkulu. Langkah-langkah penyelesaiannya dimulai dengan cara memodelkan kasus ke dalam graf dan mencari penyelesaian lintasan terpendeknya kemudian menganalisa kinerja kedua algoritma dengan membandingkannya berdasarkan hasil yang diperoleh. Berdasarkan hasil dan analisa yang diperoleh diketahui bahwa kedua algoritma memiliki kelebihan dan kekurangan masing- masing. Algoritma Dikjstra akan menentukan lintasan terpendek dengan cara mengeliminasi untuk graf yang bukan himpunan solusi sehingga perhitungannya menjadi lebih singkat, sederhana serta dapat menemukan solusi lebih cepat daripada algoritma Bellman-Ford asalkan tidak memuat bobot negatif atau cycle negatif. Algoritma BellmanFord memiliki kinerja yang lebih baik dan efektif dibandingkan algoritma Dijkstra karena terdiri dari iterasi yang melakukan pengulangan dan perbaikan lintasan untuk setiap arc yang terhubung meskipun proses perhitungannya menjadi lebih panjang
Skripsi ini membahas tentang analisis kinerja algoritma Dijkstra dan Bellman-Ford dengan studi kasus jalur lintasan angkutan umum di kota Bengkulu. Langkah-langkah penyelesaiannya dimulai dengan cara memodelkan kasus ke dalam graf dan mencari penyelesaian lintasan terpendeknya kemudian menganalisa kinerja kedua algoritma dengan membandingkannya berdasarkan hasil yang diperoleh. Berdasarkan hasil dan analisa yang diperoleh diketahui bahwa kedua algoritma memiliki kelebihan dan kekurangan masing- masing. Algoritma Dikjstra akan menentukan lintasan terpendek dengan cara mengeliminasi untuk graf yang bukan himpunan solusi sehingga perhitungannya menjadi lebih singkat, sederhana serta dapat menemukan solusi lebih cepat daripada algoritma Bellman-Ford asalkan tidak memuat bobot negatif atau cycle negatif. Algoritma BellmanFord memiliki kinerja yang lebih baik dan efektif dibandingkan algoritma Dijkstra karena terdiri dari iterasi yang melakukan pengulangan dan perbaikan lintasan untuk setiap arc yang terhubung meskipun proses perhitungannya menjadi lebih panjang
Download
book
BibTex
Latex, Jabref
cloud_download
Original Resource
url resource Institution
