Floyd-Warshall Algorithm for Web-Based Route Optimization for a Road Network Study in Medan City

Faridawaty Marpaung; Arnita; Tommy; Putri Harliana

doi:10.55927/mudima.v3i11.6674

Authors

Faridawaty Marpaung Universitas Negeri Medan
Arnita Universitas Negeri Medan
Tommy Universitas Harapan Medan
Putri Harliana Universitas Negeri Medan

DOI:

https://doi.org/10.55927/mudima.v3i11.6674

Keywords:

Shortest Path, Network Model, Floyd-Warshall Algorithm, Optimization

Abstract

The socio-demographic conditions of the region have an influence on the transportation performance in the region. This study aims to determine the shortest path between two specified points, namely the starting and the end point of several sub-districts in Medan city, especially the sub-district of Medan Amplas. To get the output, several steps are needed, namely collecting the coordinates of street names and road lengths, which is obtained from Google maps. Graphs are used to present the data. Data analysis is used by Floyd–Warshall Algorithm with HTML Web Application supported by PHP programming language, JavaScript and MySQL database. The test results using the Black Box method show that the system functionality is 100% running well. For testing, the results of the final W_ij and Z^* final matrix calculations generated by the system is same with the manual calculations. Finally, to test the reliability of the system made, the results of the reliability test show the truth of working well and it can be accepted. There are no path deviations, so that the results are as expected

References

Alam, M. A., & Faruq, M. O. (2019). Finding Shortest Path for Road Network Using Dijkstra’s Algorithm. Bangladesh Journal of Multidisciplinary Scientific Research, 1(2), 41–45. https://doi.org/10.46281/bjmsr.v1i2.366

Aziz, A., Farid, M. M., & Suryani, E. (2017). Floyd warshall algorithm with FIS Sugeno for search evacuation route optimization. 2017 International Seminar on Application for Technology of Information and Communication (ISemantic), 147–151. IEEE. https://doi.org/10.1109/ISEMANTIC.2017.8251860

Bernstein, A. (2013). Maintaining shortest paths under deletions in weighted directed graphs. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 725–734. New York, NY, USA: ACM. https://doi.org/10.1145/2488608.2488701

Dela Cruz, J. C., Magwili, G. V., Mundo, J. P. E., Gregorio, G. P. B., Lamoca, M. L. L., & Villasenor, J. A. (2016). Items-mapping and route optimization in a grocery store using Dijkstra’s, Bellman-Ford and Floyd-Warshall Algorithms. 2016 IEEE Region 10 Conference (TENCON), 243–246. IEEE. https://doi.org/10.1109/TENCON.2016.7847998

Hougardy, S. (2010). The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters, 110(8–9), 279–281. https://doi.org/10.1016/j.ipl.2010.02.001

Khamami, A., & Saputra, R. (2019). The shortest path search application based on the city transport route in Semarang using the Floyd-warshall algorithm. Journal of Physics: Conference Series, 1217(1), 012116. https://doi.org/10.1088/1742-6596/1217/1/012116

Kriswanto, Y. R., Bendi, R. K. J., & Aliyanto, A. (2014). Penentuan Jarak Terpendek Rute Transmusi dengan Algoritma Floyd-Warshall. Semantik 2014, 4(1), 209–216. Retrieved from https://publikasi.dinus.ac.id/index.php/semantik/article/view/865

Li, L. (2020). Education supply chain in the era of Industry 4.0. Systems Research and Behavioral Science, 37(4), 579–592. https://doi.org/10.1002/sres.2702

Malisan, J., Marpaung, E., Hutapea, G., Puriningsih, F. S., & Arianto, D. (2023). Development of short sea shipping in the north coast of Java Island, Indonesia as a potential market. Transportation Research Interdisciplinary Perspectives, 18, 100760. https://doi.org/10.1016/j.trip.2023.100760

Mardlootillah, H. I., Suyitno, A., & Arini, F. Y. (2014). Simulasi Algoritma Dijkstra Dalam Menangani Masalah Lintasan Terpendek Pada Graf Menggunakan Visual Basic. Unnes Journal of Mathematics, 3(1), 56–61. https://doi.org/https://doi.org/10.15294/ujm.v3i1.3285

Mariana, A. N. (2019). Implementation of the Waterfall Model for the Development of the DKI Jakarta PKK Current Mail Information System. JURIKOM (Jurnal Riset Komputer), 6(5), 453–459. https://doi.org/http://dx.doi.org/10.30865/jurikom.v6i5.1392

Nova, K., A, U., Jacob, S. S., Banu, G., Balaji, M. S. P., & S, S. (2023). Floyd–Warshalls algorithm and modified advanced encryption standard for secured communication in VANET. Measurement: Sensors, 27, 100796. https://doi.org/10.1016/j.measen.2023.100796

Ojekudo, N. A., & Akpan, N. P. (2017). Anapplication of Dijkstra’s Algorithm to shortest route problem. IOSR Journal of Mathematics, 13(1), 20–32. https://doi.org/10.9790/5728-1303012032

Pojani, D., & Stead, D. (2015). Sustainable Urban Transport in the Developing World: Beyond Megacities. Sustainability, 7(6), 7784–7805. https://doi.org/10.3390/su7067784

Putra, A. S., & Warnars, H. L. H. S. (2018). Intelligent Traffic Monitoring System (ITMS) for Smart City Based on IoT Monitoring. 2018 Indonesian Association for Pattern Recognition International Conference (INAPR), 161–165. IEEE. https://doi.org/10.1109/INAPR.2018.8626855

Sadavare, A. B., & Kulkarni, R. V. (2012). A review of application of graph theory for network. International Journal of Computer Science and Information Technologies, 3(6), 5296–5300. Retrieved from https://ijcsit.com/docs/Volume 3/vol3Issue6/ijcsit2012030601.pdf

Sahoo, L., Sen, S., Tiwary, K., Samanta, S., & Senapati, T. (2022). Modified Floyd–Warshall’s Algorithm for Maximum Connectivity in Wireless Sensor Networks under Uncertainty. Discrete Dynamics in Nature and Society, 2022, 1–11. https://doi.org/10.1155/2022/5973433

Schepers, P., Twisk, D., Fishman, E., Fyhri, A., & Jensen, A. (2017). The Dutch road to a high level of cycling safety. Safety Science, 92, 264–273. https://doi.org/10.1016/j.ssci.2015.06.005

Situmorang, R., Trilaksono, T., & Japutra, A. (2019). Friend or Foe? The complex relationship between indigenous people and policymakers regarding rural tourism in Indonesia. Journal of Hospitality and Tourism Management, 39, 20–29. https://doi.org/10.1016/j.jhtm.2019.02.001

Soemardi, B. W., & Pribadi, K. S. (2021). The Indonesian Construction Industry, 1995–2019. In Construction Industry Advance and Change: Progress in Eight Asian Economies Since 1995 (pp. 63–87). Emerald Publishing Limited. https://doi.org/10.1108/978-1-80043-504-920211004

Surya, B., Hamsina, H., Ridwan, R., Baharuddin, B., Menne, F., Fitriyah, A. T., & Rasyidi, E. S. (2020). The Complexity of Space Utilization and Environmental Pollution Control in the Main Corridor of Makassar City, South Sulawesi, Indonesia. Sustainability, 12(21), 9244. https://doi.org/10.3390/su12219244

Tristianto, C. (2018). Penggunaan metode waterfall untuk pengembangan sistem monitoring dan evaluasi pembangunan pedesaan. ESIT, 12(1), 8–22.