Pemodelan Graf Berarah Berbobot untuk Optimasi Penentuan Rute Terpendek Antar Kampus Polimarin Berbasis Algoritma Dijkstra

Helena Devi Ariyani; Khoirotun Nafillah; Kirtyana Nindita; Ngatmin Ngatmin; Sri Tutie Rahayu

doi:10.37905/euler.v14i1.37524

Pemodelan Graf Berarah Berbobot untuk Optimasi Penentuan Rute Terpendek Antar Kampus Polimarin Berbasis Algoritma Dijkstra

Helena Devi Ariyani, Khoirotun Nafillah, Kirtyana Nindita, Ngatmin Ngatmin, Sri Tutie Rahayu

Abstract

The mobility of academicians between the two geographically separated campuses of the Indonesian Maritime State Polytechnic (Polimarin), namely Campus 1 Ungaran and Campus 2 Bendan Duwur Semarang, creates travel efficiency issues due to numerous unmeasured route alternatives. This study aims to model the inter-campus road network as a weighted directed graph and apply the Dijkstra algorithm to determine the shortest route accurately and verifiably. The research employs an applied computational approach using actual distance data obtained from Google Maps (driving mode), collected on August 22, 2024, at 09:00 WIB to represent traffic conditions at that time. The process includes node identification (strategic locations), edge formation (connecting road segments), and weight assignment based on actual distances, resulting in a graph with 9 nodes and 10 edges. The iteration process is conducted in 8 steps by evaluating the minimum accumulated weight at each stage. The results indicate that the shortest path is A → B → E → G → H → I, passing through Jl. PTP Ngobo, Jl. Diponegoro–Jl. Slamet Riyadi, Jl. Moh. Yamin–Jl. Ahmad Yani, and Jl. Gatot Subroto, with a total distance of 25.80 km out of 11 possible routes. These findings demonstrate that the Dijkstra algorithm is effective for route optimization by eliminating inefficient paths through cumulative weight evaluation. Validation is performed by comparing the algorithm’s results with Google Maps recommendations based on travel distance. However, this study is limited to static data, and further development is required through the integration of dynamic traffic data.

Keywords

Dijkstra’s Algorithm; Route Optimization; Shortest Path; Weighted Directed Graph

Full Text:

PDF

References

M. K. Harahap and N. Khairina, “Pencarian Jalur Terpendek dengan Algoritma Dijkstra,” SinkrOn, vol. 2, no. 2, p. 18, 2019, doi: 10.33395/sinkron.v2i2.61.

A. D. Sabilla and A. Taufiq, “Penerapan Algoritma A* Pada WebGIS Pencarian Rute Terpendek,” J. Inf. Syst. Comput., vol. 2, no. 2, pp. 32–35, 2022, doi: 10.34001/jister.v2i2.395.

S. Sanan, L. Jain, and B. Kappor, “Shortest Path Algorithm,” Int. J. Appl. or Innov. Eng. Manag., vol. 2, no. 7, pp. 316–320, 2013.

B. Nugroho, “Aplikasi Pemrograman WEB Dinamis dengan PHP dan MySQL,” in Gava Media, Gava Media, 2019.

R. D. Gunawan, R. Napianto, R. I. Borman, and I. Hanifah, “Implementation of Dijkstra’S Algorithm in Determining the Shortest Path (Case Study: Specialist Doctor Search in Bandar Lampung),” IJISCS (International J. Inf. Syst. Comput. Sci., vol. 3, no. 3, p. 98, 2019, doi: 10.56327/ijiscs.v3i3.768.

Y. Yang, “Website Internal Link Optimization Strategy and SEO Effect Evaluation Based on Dijkstra Algorithm,” J. Comput. Signal Syst. Res., vol. 2, no. 3, p. 1, 2025, doi: 10.71222/151eah87.

D. Wahyuningsih and E. Syahreza, “Shortest Path Search Futsal Field Location With Dijkstra Algorithm,” IJCCS (Indonesian J. Comput. Cybern. Syst., vol. 12, no. 2, p. 161, 2018, doi: 10.22146/ijccs.34513.

I. P. Sari, M. F. Fahroza, M. I. Mufit, and I. F. Qathrunad, “Implementation of Dijkstra’s Algorithm to Determine the Shortest Route in a City,” J. Comput. Sci. Inf. Technol. Telecommun. Eng., vol. 2, no. 1, pp. 134–138, 2021, doi: 10.30596/jcositte.v2i1.6503.

V. N. C. Sebayang and I. Rosyida, “Implementations of Dijkstra Algorithm for Searching the Shortest Route of Ojek Online and a Fuzzy Inference System for Setting the Fare Based on Distance and Difficulty of Terrain (Case Study: in Semarang City, Indonesia),” in Proceedings of the International Conference on Mathematics, Geometry, Statistics and Computation (IC-MaGeStiC 2021), 2022, pp. 76–84. doi: 10.2991/acsr.k.220202.016.

A. Gusmao, S. H. Pramono, and S. Sunaryo, “Sistem Informasi Geografis Pariwisata Berbasis Web Dan Pencarian Jalur Terpendek Dengan P Algoritma Dijkstra,” J. EECCIS (Electrics, Electron. Commun. Control. Informatics, Syst., vol. 7, no. 2, pp. 125–130, 2013, doi: 10.21776/jeeccis.v7i2.214.

C. Ichsan, “Aplikasi Android Pencarian Mikrolet Kota Surabaya Dengan Menggunakan Algoritma Dijkstra,” Ubiquitous Comput. its Appl. J., vol. 1, pp. 19–24, 2018, doi: 10.51804/ucaiaj.v1i1.19-24.

V. N. C. Sebayang and I. Rosyida, “Implementations of Dijkstra Algorithm for Searching the Shortest Route of Ojek Online and a Fuzzy Inference System for Setting the Fare Based on Distance and Difficulty of Terrain (Case Study: in Semarang City, Indonesia),” Proc. Int. Conf. Math. Geom. Stat. Comput. (IC-MaGeStiC 2021), vol. 96, pp. 76–84, 2022, doi: 10.2991/acsr.k.220202.016.

M. Waruwu, “Pendekatan Penelitian Kualitatif: Konsep, Prosedur, Kelebihan dan Peran di Bidang Pendidikan,” Afeksi J. Penelit. dan Eval. Pendidik., vol. 5, no. 2, pp. 198–211, 2024, doi: 10.59698/afeksi.v5i2.236.

M. C. Bunaen, H. Pratiwi, and Y. F. Riti, “Penerapan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Dari Pusat Kota Surabaya Ke Tempat Bersejarah,” J. Teknol. Dan Sist. Inf. Bisnis, vol. 4, no. 1, pp. 213–223, 2022, doi: https://doi.org/10.47233/jteksis.v4i1.407.

S. Yuliani, M. R. Istambul, and E. A. Laksana, “Dijkstra’s Algorithm to Find Shortest Path of Tourist Destination in Bandung,” Turkish J. Comput. Math. Educ., vol. 12, no. 8, pp. 1163–1168, 2021, [Online]. Available: https://turcomat.org/index.php/turkbilmat/article/view/3011

A. Lusiani, E. Sartika, A. Binarto, E. Habinuddin, and I. Azis, “Determination of the Fastest Path on Logistics Distribution by Using Dijkstra Algorithm,” in Proceedings of the 2nd International Seminar on Science and Applied Technology (ISSAT 2021), 2021, pp. 246–250. doi: 10.2991/aer.k.211106.039.

L. Jabbar, E. Abass, and S. Hasan, “A Modification of Shortest Path Algorithm According to Adjustable Weights Based on Dijkstra Algorithm,” Eng. Technol. J., vol. 41, no. 2, pp. 1–16, 2022, doi: 10.30684/etj.2022.136107.1296.

L. Y. Sipayung, C. R. Sinaga, and A. C. Sagala, “Application of Dijkstra’s Algorithm to Determine the Shortest Route from City Center to Medan City Tourist Attractions,” J. Comput. Networks, Archit. High Perform. Comput., vol. 5, no. 2, pp. 648–655, 2023, doi: 10.47709/cnahpc.v5i2.2699.

Suardinata, R. Rusmi, and M. A. Lubis, “Determining Travel Time and Fastest Route Using Dijkstra Algorithm and Google Map,” J. Sist. Inf., vol. 11, no. 1, pp. 496–505, 2022, doi: 10.32520/stmsi.v11i2.1836.

A. Ardiansyah, A. M. Nasution, and M. Iqbal, “Comparative Analysis of Dijkstra and A* Algorithms for Determining the Shortest Route,” bit-Tech, vol. 8, no. 2, pp. 2974–2983, 2025, doi: 10.32877/bt.v8i2.3474.

B. He, “Application of Dijkstra algorithm in finding the shortest path,” J. Phys. Conf. Ser., vol. 2181, no. 1, 2022, doi: 10.1088/1742-6596/2181/1/012005.

DOI: https://doi.org/10.37905/euler.v14i1.37524