Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm
DOI:
https://doi.org/10.21512/comtech.v7i3.2534Keywords:
shortest path, dynamic weight, Dijkstra’s algorithm, graph, digraphAbstract
Shortest path algorithms have been long applied to solve daily problems by selecting the most feasible route with minimum cost or time. However, some of the problems are not simple. This study applied the case using Dijkstra's algorithm on a graph representing street routes with two possible digraphs: one-way and twoway. Each cost was able to be changed anytime, representing the change in traffic condition. Results show that the usage of one way digraph in mapping the route does make the goal possible to reach, while the usage of twoway digraph may cause confusion although it is probably the possible choice in the real world. Both experiments showed that there are no additional computation stresses in re-calculating the shortest path while going halfway to reach the goal.Plum Analytics
References
Astuti, Y. D. (2015). Dasar Teori Grafin “Logika dan Algoritma” lecture notes. Retrieved February 18, 2015 from http://rifki_kosasih.staff.gunadarma.ac.id/Downloads/files/37568/Bab+1++Dasar+Teori+Graf.pdf
Arifianto, S. (2012). Sistem Aplikasi Penentuan Rute Terpendek Pada Jaringan Multi Moda Transportasi Umum Menggunakan Algoritma Dijkstra (Master’s thesis). Semarang: Program Studi Sistem Informasi, Program Pascasarjana Universitas Diponegoro
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271
Djojo, M. A., & Karyono. (2013). Pengukuran Beban Komputasi Algoritma Dijkstra, A*, dan Floyd-Warshall pada Perangkat Android. ULTIMA Computing, 5(1), 13-17.
Głabowski, M., Musznicki, B., Nowak, P., & Zwierzykowski, P. (2013). Efficiency Evaluation of Shortest Path Algorithms. In The Ninth Advanced International Conference on Telecommunications (AICT) 2013 Proceedings (pp. 154-160). Rome, Italy.
Harju, T. (2011). Lecture Notes on Graph Theory, Department of Mathematics, University of Turku, Finland. Retrieved February 18, 2015 from http://cs.bme.hu/fcs/graphtheory.pdf
Prasetyo, V. Z. (2013). Penerapan Algoritma Dijkstra Untuk Perutean Adaptif Pada Jaringan Pendistribusian Air PDAM di Kabupaten Demak (Bachelor’s thesis). Semarang: Jurusan Matematika, Fakultas MIPA, Universitas Negeri Semarang
Rodrigue, J-P., & Ducruet, C. (2015). Graph Theory: Measures and Indices. Retrieved February 18, 2015 from https://people.hofstra.edu/geotrans/eng/methods/ch1m3en.html
Ruohonen, K. (2013). Graph Theory. Retrieved February 18, 2015 from http://math.tut.fi/ ~ruohonen/GT_English.pdf
Sholichin, R., Yasindan, M., & Oktoviana, L. T. (2012). Implementasi Algoritma Dijkstra Dalam Pencarian Lintasan Terpendek Lokasi Rumah Sakit, Hotel Dan Terminal Kota Malang Berbasis Web. Jurnal Online Universitas Negeri Malang, (Online).
Sunaryo, Siang, J. J., & Chrismanto, A. R. (2012). Pencarian Jalur Terpendek Antar Kota Di Jawa Tengah Dan D.I. Yogyakarta Dengan Algoritma Dijkstra Via SMS Gateway (Bachelor’s thesis). Yogyakarta: Program Studi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Kristen Duta Wacana
Triansyah, F. A. (2013). Implementasi Algoritma Dijkstra Dalam Aplikasi Untuk Menentukan Lintasan Terpendek Jalan Darat Antar Kota Di Sumatera Bagian Selatan. Jurnal Sistem Informasi (JSI), 5(2), 611-621.
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
a. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License - Share Alike that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
b. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
c. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
USER RIGHTS
All articles published Open Access will be immediately and permanently free for everyone to read and download. We are continuously working with our author communities to select the best choice of license options, currently being defined for this journal as follows:
