Dijkstra Algorithm-Based Shortest Path Optimization for Multi-Destination Tourism Routes in Samosir Regency: A Google Maps-Driven Case Study
DOI:
https://doi.org/10.35870/ijsecs.v6i2.7604Keywords:
Dijkstra's Algorithm, Graph Theory, Shortest Path, Tourism Route Planning, Samosir Regency, Google MapsAbstract
Samosir Regency offers various natural and cultural tourism destinations distributed across several sub-districts. The distribution of these destinations and their road connections can make it difficult for visitors to determine efficient travel routes. This study aimed to determine the shortest route from Tano Ponggol to Hadabuan Nasogo Waterfall using a weighted graph approach and Dijkstra's algorithm based on distance data obtained from Google Maps. Nine tourist attractions were modeled as vertices and thirteen connecting routes as weighted edges representing travel distances for four-wheeled vehicles. Distance data were collected from Google Maps in April 2025 and processed using Dijkstra's algorithm. The results showed that the shortest route was A→B→D→E→H→I, with a total distance of 100.1 km and six of the nine attractions included in the route. Compared with the sequential baseline route that passes through all nine destinations (A→B→C→D→E→F→G→H→I), the shortest route reduced the travel distance by 31.6 km (24%) and the estimated travel time by 1 hour and 3 minutes (27%). However, the shorter route bypassed three attractions (C, F, and G), showing that a shortest-path approach does not ensure coverage of all tourism destinations. Dijkstra's algorithm is therefore suitable for determining the shortest route between a selected source and destination, while tourists who intend to visit multiple destinations may require a multi-stop optimization approach, such as the Traveling Salesman Problem. The findings provide a route recommendation for tourism travel in Samosir Regency and illustrate the need to select an optimization method according to the intended travel objective.
Downloads
References
Agusnur, A. (2025). Penggunaan teori graf dalam optimasi jaringan transportasi kota. Jurnal Matematika dan Aplikasi, 1(1), 29–35.
Agustiono, W., & Hermanto, K. D. (2010). Pemanfaatan teknologi Google Maps untuk penyelesaian online travelling salesman problem (TSP) berbasis geografis dengan menggunakan algoritma heuristik. JUTI: Jurnal Ilmiah Teknologi Informasi, 8(2), 38–42. https://doi.org/10.12962/j24068535.v8i2.a315
Andini, M., Kultsum, R. U., Raihan, M. H. R., & Lestari, S. (2025). Optimasi pencarian rute terpendek menggunakan algoritma Dijkstra. Journal of Information System, Applied, Management, Accounting and Research, 9(1), 290–302. https://doi.org/10.52362/jisamar.v9i1.1746
Andriati, D. A., Dariato, E., & Hafizh, R. (2025). Implementasi teori graf dan optimisasi algoritma Dijkstra, BFS, dan DFS dalam menentukan rute terpendek jaringan bengkel di Jakarta berbasis Google Maps. Jurnal Multimedia dan Teknologi Informasi (Jatilima), 7(3), 674–684. https://doi.org/10.54209/jatilima.v7i03.1654
Angul, A., Fallo, D., Tanggo, K. V., Belo, I. N. A., & Hoar, F. (2025). Implementasi algoritma Dijkstra dan greedy dalam penyelesaian masalah rute terpendek. Jurnal Kridatama Sains dan Teknologi, 7(1), 489–496. https://doi.org/10.53863/kst.v7i01.1654
Barus, Y. L. B., Harianja, R. P., Sinaga, F., Nababan, A., & Sihombing, N. E. (2026). Pemanfaatan digital marketing dalam meningkatkan potensi pariwisata pada Dinas Kebudayaan dan Pariwisata Kabupaten Samosir. Jurnal Pengabdian Kepada Masyarakat “PARHOBAS”, 1(1), 126–133.
Cantona, A., Fauziah, & Winarsih. (2020). Implementasi algoritma Dijkstra pada pencarian rute terpendek ke museum di Jakarta. Jurnal Teknologi dan Manajemen Informatika, 6(1), 27–34. https://doi.org/10.26905/jtmi.v6i1.3837
Fitriya B, W. A., Sumardi, S. R., Paranoan, N. R., & Allo, C. B. G. (2023). Penentuan rute di aplikasi Google Maps dengan menggunakan graf dan algoritma Prim. KOLONI: Jurnal Multidisiplin Ilmu, 2(1), 220–225. https://doi.org/10.31004/koloni.v2i1.434
Hambali, F. U., & Wismarini, T. D. (2022). Metode network analisis pencarian rute optimal dengan algoritma Dijkstra kunjungan Desa Wisata Wonolopo dengan jarak tempuh berdasar metode Euclidean distance. Jurnal Mahajana Informasi, 7(1), 1–8. https://doi.org/10.51544/jurnalmi.v7i1.2949
Kurniawan, E. K., & Atmojo, W. T. (2025). Penerapan algoritma Dijkstra dalam penentuan rute terpendek kunjungan wisata Jakarta. ZONAsi: Jurnal Sistem Informasi, 7(2), 445–454. https://doi.org/10.31849/zn.v7i2.26342
Lakutu, N. F., Katili, M. R., Mahmud, S. L., & Yahya, N. I. (2023). Algoritma Dijkstra dan algoritma greedy untuk optimasi rute pengiriman barang pada Kantor Pos Gorontalo. EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi, 11(1), 55–65. https://doi.org/10.34312/euler.v11i1.18244
Manalu, E., Napitupulu, V., Afriyani, M., & Butar-butar, H. B. (2025). Penerapan algoritma Dijkstra jalur terpendek antar objek wisata Danau Toba. Jurnal Manajemen Informatika Jayakarta, 5(4), 375–386. https://doi.org/10.52362/jmijayakarta.v5i4.2002
Maulana, A. (2025). Penerapan Kruskal minimum spanning tree pada optimasi rute wisata Bojong Kabupaten Tegal. Jurnal Rekayasa Informatika (JRIT), 2(1), 36–45.
Muharrom, M. (2020). Implementasi algoritma Dijkstra dalam penentuan jalur terpendek: Studi kasus jarak tempat kuliah terdekat. Indonesian Journal of Business Intelligence, 3(1), 25–30. https://doi.org/10.21927/ijubi.v3i1.1229
Musabbikhah, L., & Yuliantari, R. V. (2022). Review artikel: Analisis penggunaan algoritma Dijkstra untuk mencari rute terpendek di rumah sakit. Edu Elektrika Journal, 11(1), 1–5. https://doi.org/10.15294/eej.v11i1.53460
Prakoso, A. B., Ariyanto, Y., & Hayati Ririd, A. R. T. (2017). Optimasi rute lokasi wisata Kota Malang menggunakan metode algoritma genetika. Jurnal Informatika Polinema, 3(3), 48–52. https://doi.org/10.33795/jip.v3i3.34
Pramadjaya, A., & Rohmawati, I. (2025). Analisis rute terpendek menuju Universitas Pamulang dengan implementasi algoritma Dijkstra: Analysis of the shortest route to Universitas Pamulang using the implementation of Dijkstra’s algorithm. MALCOM: Indonesian Journal of Machine Learning and Computer Science, 5(3), 953–961. https://doi.org/10.57152/malcom.v5i3.1983
Rahmawati, D., Putri, M., Rosmawati, & Hakim, F. (2023). Analysis of the fastest cost and route using the graph theory and network analysis. Enthusiastic: International Journal of Applied Statistics and Data Science, 3(2), 202–211. https://doi.org/10.20885/enthusiastic.vol3.iss2.art7
Sabilla, A. D., & Taufiq, A. (2022). Penerapan algoritma A* pada WebGIS pencarian rute terpendek. Journal of Information System and Computer, 2(2), 32–35. https://doi.org/10.34001/jister.v2i2.395
Safetra, M. F. C., Desviona, N., Helmina, Rianti, A., & Prayogi, M. R. (2026). Penerapan teori graf dalam kehidupan sehari-hari. Algoritma: Jurnal Matematika, Ilmu Pengetahuan Alam, Kebumian dan Angkasa, 4(1), 52–68. https://doi.org/10.62383/algoritma.v4i1.923
Susanto, B. M., & Hariyanto, A. (2023). Aplikasi penentuan rute terpendek pengambilan sampah berbasis Internet of Things terintegrasi dengan Google Maps API. Angkasa: Jurnal Ilmiah Bidang Teknologi, 15(1), 133–140. https://doi.org/10.28989/angkasa.v15i1.1651
Taneo, R. E., Ndun, R., Fallo, D. Y. A., & Do'o, F. (2025). Optimasi jalur terpendek menggunakan algoritma Dijkstra dan greedy pada sistem informasi geografis. Jurnal Kridatama Sains dan Teknologi, 7(1), 572–582. https://doi.org/10.53863/kst.v7i01.1664
Rande, P., Witin, S. S. G., Permatasari, W. D., Aminah, N., Amijaya, F. D. T., & Putri, D. F. (2025). Penerapan algoritma branch and bound untuk optimasi rute wisata di Kalimantan Timur berdasarkan traveling salesman problem. MATHunesa: Jurnal Ilmiah Matematika, 13(2), 197–205.
Downloads
Published
Issue
Section
Categories
License
Copyright (c) 2026 Yesy Simanjuntak, Fadillah Amanah, Suvriadi Panggabean
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
1. Copyright Retention and Open Access License
Authors retain copyright of their work and grant the journal non-exclusive right of first publication under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
This license allows unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
2. Rights Granted Under CC BY 4.0
Under this license, readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material for any purpose, including commercial use
- No additional restrictions — the licensor cannot revoke these freedoms as long as license terms are followed
3. Attribution Requirements
All uses must include:
- Proper citation of the original work
- Link to the Creative Commons license
- Indication if changes were made to the original work
- No suggestion that the licensor endorses the user or their use
4. Additional Distribution Rights
Authors may:
- Deposit the published version in institutional repositories
- Share through academic social networks
- Include in books, monographs, or other publications
- Post on personal or institutional websites
Requirement: All additional distributions must maintain the CC BY 4.0 license and proper attribution.
5. Self-Archiving and Pre-Print Sharing
Authors are encouraged to:
- Share pre-prints and post-prints online
- Deposit in subject-specific repositories (e.g., arXiv, bioRxiv)
- Engage in scholarly communication throughout the publication process
6. Open Access Commitment
This journal provides immediate open access to all content, supporting the global exchange of knowledge without financial, legal, or technical barriers.
