Pencarian semua pasangan jalur terpendek dengan Algoritma Dijkstra yang dimodifikasi

Abstract

Menemukan jalur terpendek merupakan masalah mendasar dalam teori graf. Pencarian jalur terpendek dapat diterapkan dalam banyak bidang seperti ilmu komputer, teknik transportasi, maupun analisis jaringan. Salah satu contoh aplikasi dalam bidang transportasi adalah pencarian jalur terpendek dari sebuah kota ke kota lainnya. Walaupun digunakan dalam banyak bidang, tetapi pencarian jalur terpendek pada jaringan kompleks berskala besar masih membutuhkan waktu pengerjaan yang lama. Salah satu algoritma yang dapat digunakan untuk menyelesaikan masalah pencarian jalur terpendek adalah Algoritma Dijkstra.

Akan tetapi, Algoritma Dijkstra kurang cocok jika diterapkan dalam jaringan kompleks berskala besar karena jaringan kompleks berskala besar memiliki sisi yang banyak. Jika menggunakan Algoritma Dijkstra biasa, maka semua sisi tersebut akan dihitung berulang-ulang. Algoritma Dijkstra dapat dikembangkan dengan sedikit modifikasi agar sesuai dengan karakteristik jaringan kompleks berskala besar, sehingga setiap sisi pada jaringan kompleks berskala besar tidak dihitung berulang-ulang. Modifikasi yang dilakukan adalah memanfaatkan informasi yang sudah didapatkan pada langkah sebelumnya, sehingga dapat mempercepat langkah akhir perhitungan. Selain itu, Algoritma Dijkstra modifikasi tersebut digunakan pada tiga algoritma lainnya yang berfungsi untuk memanggil Algoritma Dijkstra modifikasi yaitu Basic Algorithm, Optimized Algorithm, dan Adaptive Algorithm. Pada ketiga algoritma tersebut, memiliki cara yang berbeda dalam pengurutan simpul yang akan dihitung.

Perangkat lunak yang dibangun dapat melakukan pencarian semua pasangan jalur terpendek dengan menggunakan Algoritma Dijkstra biasa maupun Algoritma Dijkstra modifikasi. Pengguna hanya perlu memasukkan graf yang akan digunakan dan memilih pilihan algoritma yang tersedia. Setelah itu, pengguna akan mendapatkan jalur terpendek dari semua pasangan simpul dan waktu pengerjaan dari algoritma tersebut.

Berdasarkan pengujian yang telah dilakukan, waktu pengerjaan dari Algoritma Dijkstra modifikasi pada Basic Algorithm lebih baik dibandingkan Algoritma Dijkstra biasa. Waktu pengerjaan Adaptive Algorithm pada graf yang memiliki simpul yang sedikit lebih baik dibandingkan Algoritma Dijkstra biasa, tetapi pada graf dengan simpul yang banyak Adaptive Algorithm lebih buruk. Hasil pengujian pada Optimized Algorithm menunjukkan waktu pengerjaan yang lebih lama dibandingkan Algoritma Dijkstra biasa. Pada Basic Algorithm, Optimized Algorithm, dan Adaptive Algorithm, terdapat parameter yang dapat mempengaruhi performa dari masing-masing algoritma.