Ferdifiansyah, Finsa (2013) Perbandingan Algoritma Dijkstra Dan Algoritma Ant Colony Dalam Penentuan Jalur Terpendek. Sarjana thesis, Universitas Brawijaya.
Abstract
Pencarian jalur terpendek merupakan pencarian sebuah jalur pada graf berbobot yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut. Dengan begitu jalur yang dihasilkan merupakan jalur yang memiliki bobot atau jarak yang paling sedikit. Salah satu penerapan pencarian jalur terpendek terdapat pada aktivitas maskapai penerbangan yang mana jalur-jalur antar kota yang dilewatinya akan membentuk suatu graf berarah dan berbobot. Dari graf yang terbentuk inilah akan diproses menggunakan algoritma Dijkstra dan Ant Colony untuk menentukan jalur terpendek dari suatu kota ke kota yang lain. Pada proses Algoritma, Dijkstra memerlukan data jarak setiap kota terlebih dahulu sebelum memulai proses algortimanya. Sedangkan pada Algoritma Ant Colony, tidak memerlukan jarak setiap kota karena pada Ant Colony jarak antar kota dihitung setelah semut menyelesaikan perjalanannya. Sehingga Algoritma Dijkstra hanya bisa berjalan jika terlebih dahulu diketahui jarak tiap kota, sedangkan pada Algoritma Ant Colony tidak memerlukan jarak tiap kota untuk menjalankan prosesnya. Dari hasil proses kedua algoritma diketahui jalur yang dihasilkan oleh algoritma Dijkstra lebih konsisten dan tepat daripada algoritma Ant Colony yang mana memberikan hasil yang belum tentu sama dalam setiap prosesnya. Rata-rata memory yang digunakan pada algoritma Dijkstra sebesar 82,204 KB dan algoritma Ant Colony sebesar 90,404 KB. Sedangkan dari analisa kompleksitas waktu pada algoritma Dijkstra diperoleh persamaan ( ) ( ) dan pada Algoritma Ant Colony persamaannya ( ) ( )
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/FT/2013/207/051306290 |
| Subjects: | 600 Technology (Applied sciences) > 621 Applied physics > 621.3 Electrical, magnetic, optical, communications, computer engineering; electronics, lighting |
| Divisions: | Fakultas Teknik > Teknik Elektro |
| Depositing User: | Endang Susworini |
| Date Deposited: | 04 Sep 2013 15:25 |
| Last Modified: | 21 Oct 2021 04:25 |
| URI: | http://repository.ub.ac.id/id/eprint/141928 |
Preview |
Text
051306290.pdf Download (4MB) | Preview |
Actions (login required)
 |
View Item |