Algoritma modifikasi ernesto dalam menyelesaikan masalah jalur terpendek ke - k = Yen s algorithm and its modification on solve the - k th shortest path problem
| Format: | Bachelors |
|---|---|
| Terbitan: |
Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia
, 2014
|
| Subjects: | |
| Online Access: |
http://lib.ui.ac.id/file?file=digital/2015-10/20402561-S58617-Alamsyah Koto Hanza.pdf |
Daftar Isi:
- [Masalah jalur terpendek berkembang dengan adanya masalah baru dalam konteks Alternate Routing, yaitu pencarian jalur terpendek ke-2, ke-3, dan seterusnya. Bentuk umum dari masalah Alternate Routing tersebut adalah The K-th Shortest Path Problem, dengan salah satu algoritma yang dapat menyelesaikannya adalah Algoritma Yen. Algoritma Yen dijamin dapat menyelesaikan masalah tersebut dengan menggunakan prinsip bahwa jalur terpendek ke-K merupakan deviasi dari jalur terpendek ke-J, untuk J<K. Kemudian Ernesto memodifikasi algoritma tersebut menggunakan fungsi deviasi untuk mengurangi iterasi pada algoritma Yen. Modifikasi ini juga menggunakan algoritma pelabelan sebagai indikasi adanya jalur. Pada skripsi ini dibahas validitas dari algoritma yen dan modifikasi oleh Ernesto, serta membandingkan running time program dari kedua algoritma tersebut. Hasil perbandingan running time menunjukkan bahwa untuk kasus rata-rata, algoritma modifikasi merupakan algoritma yang lebih cepat dan efisien. Hasil program kedua algoritma tersebut juga menunjukan bahwa solusi dari adalah The K-th Shortest Path Problem tidak unik. , Shortest path problem has new development in contex of Alternate Routing, such as to find the second shortest path, the third shortest path and so on. Generalization of this problem is The K-th Shortest Path Problem. One of algorithms that solve this kind of problem is Yen’s Algorithm. Yen’s Algorithm is guaranteed can solve that problem by use principle that K-th shortest path is deviation of J-th shortest path, for J<K. Several years later, Yen’s algorithm had been modificated by Ernesto for decrease it’s iteration. Modification of Yen’s algorithm also use Labeling algorithm to indicate the path. On this skripsi will be discussed about validity of Yen’s algorithm and it’s modification, also compare running time of programs of those algorithm. Comparing results of running time shown that, in average-case, modification of algorithm is more efficient and fastest than Yen’s algorithm. Output results of those programs also shown that solution of The K-th Shortest Path Problem is not unique. ]