## Indonesian Journal of Business Intelligence
Volume 7 | Issue 1 | June (2024)
ISSN 2621-3915 (PRINT) , ISSN 2621-3923 (ONLINE) , Published by Alma Ata University Press IJUBI Indonesian Journal ---- of ----
Business Intelligence

## PENERAPAN ALGORITMA DIJKSTRA UNTUK MENENTUKAN RUTE TERPENDEK TEMPAT TINGGAL KE KAMPUS 2 UIN SUNAN AMPEL SURABAYA
Galang Nurendrawan Ramadhan 1* , Raihan Khaira Alma Bachrun 2 , Achmad Syaifulloh 3 1,2,3 Matematika, Fakultas Sains dan Teknologi, UIN Sunan Ampel Surabaya.
* galangnurendrawan25@gmail.com
Jl. Dr. Ir. H. Soekarno No.682 Kec. Gn. Anyar, Surabaya, Jawa Timur, Indonesia
Keywords:
Dijkstra
Algorithm, graph, determining the shortest route. Abstract
Dijkstra calculations can create effective productive time in determining the distance between systems when compared to manual calculations because the Dijkstra algorithm provides output in the form of the fastest and shortest path from the origin to the destination. The aim of this focus will be to discuss the application of the Dijkstra Algorithm to determine the shortest route for residence to Campus 2 of UIN Sunan Ampel Surabaya. This research method is observation using Google Maps to find out the distance of the route taken. The results of this research were successful in finding the shortest route between JL. Jojoran 1 and Campus 2 of UIN Sunan Ampel
Surabaya, namely via the first route with a distance of 11.5 km, but this is not the fastest route. Various environmental factors such as traffic jams, weather conditions, accidents, poor road conditions, and other factors can affect the speed of travel to the destination, so they need to be considered carefully in determining the fastest route.
Article history:
Received : 21 December 2023 Revised : 28 June 2024 Accepted : 30 June 2024

## Kata Kunci:
Algoritma Dijkstra, graf, penentuan
rute terpendek.

## Abstrak
Perhitungan Dijkstra dapat menciptakan waktu produktif yang efektif dalam memastikan jarak antar sistem jika dibandingkan dengan perhitungan manual karena Algoritma Dijkstra ini memberikan keluaran berupa jalur tercepat dan terpendek dari tempat asal menuju tempat tujuan. Tujuan dari fokus ini akan membahas mengenai penerapan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Tempat Tinggal Ke Kampus 2 UIN Sunan Ampel Surabaya. Metode penelitian ini yakni observasi dengan menggunakan Google Maps untuk mengetahui jauh rute yang ditempuh. Hasil dari penelitian ini yakni berhasil menemukan jalur terpendek antara JL. Jojoran 1 dan Kampus2
UIN Sunan Ampel Surabaya, yakni melalui rute pertama dengan jarak tempuh 11,5 km namun bukan berarti jalur tercepat. Berbagai faktor lingkungan seperti kemacetan, kondisi cuaca, kecelakaan, kondisi jalan yang buruk, dan faktor-faktor lainnya dapat mempengaruhi kecepatan perjalanan menuju tujuan, sehingga perlu dipertimbangkan dengan cermat dalam menentukan rute tercepat.

## Pendahuluan
Surabaya merupakan kota dengan luas wilayah terbesar ke-dua di Indonesia yang tepatnya terletak di Pulau Jawa. Kota Surabaya juga merupakan Ibu kota dari Jawa Timur. Karena statusnya sebagai kota besar maka kemacetan menjadi hal yang wajar dan pemandangan sehari-hari. Kepadatan penduduk yang tinggi dan berbagai macam aktivitas menjadikan kota tersebut selalu ramai dari lalu lintas manusia. Fleksibilitas yang sangat tinggi ini sebagian besar disebabkan oleh kurangnya sarana dan prasarana jalan. Maka dari itu, dibutuhkan penyelesaian yang tepat yang dapat bekerja dengan fleksibilitas ini. Salah satu jalan keluarnya adalah dengan menambahkan fasilitas jalan dan kerangka kerja yang saat ini sangat terbatas. Salah satu alternatif adalah menggunakan kebijaksanaan pribadi dalam memilih dan memanfaatkan metode yang dapat diakses oleh kita sendiri, sehingga mempermudah dan memaksimalkan pemanfaatan sarana yang dapat diakses. Berbagai solusi sudah dilakukan pemerintah daerah setempat agar masalah kemacetan dapat teratasi, termasuk dengan menerapkan Area Traffic Light Framework (ATCS), dan lebih jauh lagi dengan memperkenalkan Traffic Public Declaration (TPA) di berbagai ruas jalan demi lancarnya lalu lintas. Meskipun demikian, kemacetan tetap saja terjadi [1]. Menurut Wibowo & Wicaksono (2012), pengguna jalan harus dapat mencari jalan keluar yang berbeda, yaitu dengan memilih jalan mana saja yang akan dilalui untuk mencari rute terdekat atau tujuan dengan jarak terpendek. Untuk itu algoritma yang dapat dipakai untuk menentukan jarak terpendek dari suatu lintasan yakni Algortima Dijkstra [2]. Algoritma
Dijkstra digunakan untuk membuktikan jarak paling pendek dari pilihan rute yang tersedia. Algoritma Dijkstra mengevaluasi semua potensi bobot minimum untuk setiap titik. Algoritma Dijkstra merupakan tipe algoritma rakus (greedy algorithm) berprinsip menggunakan layanan minimum pada sejumlah jarak yang ada guna memberikan berbagai solusi untuk mengetahui jarak terpendek [3]. Aplikasi algoritma Dijkstra sering digunakan untuk berbagai kegiatan keseharian. Sistem diberikan pilihan jarak yang dapat ditempuh menggunakan algoritma
Dijkstra; sistem kemudian memilih jarak terpendek yang dapat ditempuh paling cepat dan menunjukkan peta untuk pengguna. Perhitungan Dijkstra bisa menciptakan waktu produktif yang efektif dalam memastikan jarak antar sistem jika dibandingkan dengan perhitungan manual [4].
Sudah banyak penelitian yang membahas penerapan algoritma Dijkstra ini untuk berbagai permasalahan seperti pemetaan lokasi, pencarian lokasi, maupun penentuan jarak terdekat dari suatu lokasi ke lokasi yang lain. Penelitian yang dilakukan oleh Muhammad Muharrom (2020) telah berhasil menemukan cara untuk menentukan rute tercepat dan terdekat antar dua lokasi dengan Algoritma Dijkstra. Penelitian ini menggunakan masukan yang terdiri dari simpul awal dan akhir, bersama dengan suatu graf yang menggambarkan simpul sebagai node dan jalur sebagai penghubung antar simpul [5]. Atas dasar latar belakang yang telah diuraikan, peneliti merasa berminat untuk melakukan penelitian yang bertujuan untuk menemukan jalur terpendek menggunakan metode
Algoritma Dijkstra. Pada peneltian ini akan dicari rute terpendek dari tempat tinggal peneliti ke kampus. Maka dari itu peneliti mengambil judul “ Penerapan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Tempat Tinggal Ke Kampus 2 UIN Sunan Ampel Surabaya ” . Penelitian ini bertujuan untuk mengetahui jalur menuju tujuan, utamanya mengetahui pilihan rute terpendek sehingga peneliti bisa sampai tujuan dalam tepat waktu. Selain itu, peneliti bisa menghemat biaya, bahan bakar kendaraan, dan khususnya waktu. Hasil yang didapat dari penelitian ini berupa representasi graf berarah untuk rute seluruh jalan dari Jojoran 1 menuju Kampus 2 UIN Sunan Ampel Surabaya, kemudian menentukan jarak terpendek menggunakan algoritma Dijkstra. Keunggulan dari algoritma Dijkstra adalah kemampuannya untuk menemukan jalur terpendek dalam graf berbobot yang bobotnya bernilai lebih besar dari nol (positif), dari semua titik yang telah ditentukan. Hal ini memungkinkan kita untuk menemukan rute terpendek dari titik awal ke titik tujuan. Pada akhirnya sangat membantu peneliti dalam menentukan rute terpendek dengan praktis.

## Metode
Peneliti ini dilakukan dengan cara observasi, dan studi pustaka. Observasi dengan cara melihat secara langsung perjalanan yang dilalui dan selanjutnya memverifikasinya dengan menggunakan Google Maps untuk mengetahui jauh rute yang ditempuh. Observasi ini meliputi rute yang dimulai dari Jalan Jojoran 1 menuju Kampus 2 UIN Sunan Ampel Surabaya, yang diukur berdasarkan peta di Google Maps.
Studi Pustaka Tahapan yang dilakukan oleh peneliti untuk mengumpulkan materi yang akan berguna dalam perancangan program adalah dengan melakukan pengumpulan melalui sumber literatur berupa buku, jurnal, dan informasi yang terdapat pada internet yang berkaitan dengan judul penelitian. Fokus dalam pengumpulan tersebut adalah pada buku-buku yang dapat menunjang materi untuk penelitian ini. Berikut ini adalah skema rancangan penelitian yang diusulkan:

## Gambar 1. Alur Penelitian

## Pembahasan
Penggunaan yang paling terkenal dari teori graf adalah penentuan lintasan terpendek, penentuan lintasan terpendek adalah masalah yang secara umum telah diperiksa dan direnungkan mulai sekitar tahun 1950.
Penemuan jarak terdekat sudah
diimplementasikan pada berbagai bidang guna merampingkan penyajian kerangka kerja. Salah satu topik menarik yang layak untuk didiskusikan adalah masalah transportasi yang melibatkan pencarian lintasan terpendek. Telah diketahui bahwa untuk mencapai suatu tujuan, sebuah kota dapat dicapai melalui beberapa cara. Untuk melacak tujuan dengan jarak yang paling singkat; jarak terpendek dapat diuraikan sebagai beban dasar dari sebuah lintasan, yang merupakan jumlah beban dari semua segmen melingkar yang membentuk lintasan tersebut [6].
Algoritma Dijsktra sangat populer dalam menyelesaikan masalah pencarian lintasan terpendek. Metode ini bermanfaat ketika kita hendak mencari jarak terpendek antara dua simpul dalam graf yang memiliki nilai bobot positif. Namun, apabila terdapat bobot negatif, hasil solusinya akan menjadi tak terbatas (infiniti) [5]. Node atau simpul yang digunakan dalam Algoritma Dijkstra berguna untuk menemukan jalur terpendek dalam graf berarah. Berikut adalah beberapa langkah dasar dari Algoritma Dijkstra:
1. Langkah pertama yang akan dilakukan yakni menentukan node atau simpul sebagai titik awal, lalu melakukan analisis pada graf guna menemukan rute paling pendek antara titik awal dengan titik-titik lain yang terdapat pada graf. 2. Kemudian Algoritma akan mulai menghitung rute terpendek dari setiap titik yang diketahui ke titik awal. Titik yang diketahui memiliki jarak paling pendek akan ditandai dengan tanda "dikunjungi" dan ditambahkan ke rute. 3. Selanjutnya proses ini akan diteruskan hingga seluruh titik dalam graf telah ditambahkan ke dalam rute. Dengan demikian, kita akan mendapatkan ruteyang terhubung dengan titik awal ke seluruh titik lainnya dengan mengikuti rute terpendek yang mungkin untuk mencapai semua titik [7].

## Hasil
Jarak dalam kilometer antar jalan diambil dari data awal Google Maps, dengan nama jalan sebagai titik dan jarak antara setiap jalan sebagai bobot sisi.

## Gambar 2. Sampel Awal yang Didapat dari Google Maps
Peneliti melakukan studi mengenai jarak tempuh dari jalan Jojoran 1 ke Kampus 2 UIN Sunan Ampel Surabaya. Ada banyak rute yang dapat dipilih untuk mencapai tujuan tersebut, namun peneliti memilih untuk menampilkan beberapa titik persimpangan yang dapat dilihat pada grafik berdasarkan titik-titik tujuan dan jarak tempuh (dalam kilometer) yang ditempuh. Berikut ini adalah grafik yang dibuat oleh peneliti.

## Gambar 3. Gambar Graf Jalan Jojoran 1 Menuju Kampus 2 UIN Sunan Ampel Surabaya
Keterangan: A = JL. Jojoran 1 B = JL. Dharmahusada Indah C = JL. Kertajaya Indah D = JL. Dr. Ir. H. Soekarno
E = JL. Tol Waru Juanda
F = Kampus 2 UIN Sunan Ampel Surabaya G = JL. Karang Menjangan H = JL. Raya Menur I = JL. Raya Manyar J = JL. Raya Nginden K = JL. Panjang Jiwo L = JL. Raya Kedung Baruk
M = JL. Raya Kalirungkut N = JL. Raya Kalirungkut Kidul
O = JL. Raya Rungkut Tengah P = JL. Raya Rungkut Menaggal Q = JL. Raya Taman Asri R = JL. Arah Surabaya S = JL. Raya Menur Pumpungan T = JL. Arief Rahman Hakim Pada gambar di atas, terlihat jalur-jalur yang dapat dilalui beserta jaraknya (dalam kilometer) jikamelewati jalur tersebut. Peneliti menjelaskan jalur-jalur tersebut sebagai berikut: Tabel 1. Rute 1 Rute 1 Jarak JL. Jojoran 1 0 JL. Dharmahusada Indah 0,6 JL. Kertajaya Indah 1 JL. Dr. Ir. H. Soekarno 1 JL. Tol Waru Juanda 8 Kampus 2 UIN Sunan Ampel Surabaya 0,5 Total 11,5 Tabel 2. Rute 2 Rute 2 Jarak JL. Jojoran 1 0 JL. Karang Menjangan 0,55 JL. Raya Menur 0,35 JL. Raya Manyar 1,5 JL. Raya Nginden 1,3 JL. Panjang Jiwo 0,8 JL. Raya Kedung Baruk 0,9 JL. Dr. Ir. H. Soekarno 1,2 JL. Tol Waru Juanda 8 Kampus 2 UIN Sunan Ampel Surabaya 0,5 Total 15,1 Tabel 3. Rute 3 Rute 3 Jarak JL. Jojoran 1 0 JL. Karang Menjangan 0,55 JL. Raya Menur 0,35 JL. Raya Manyar 1,5 JL. Raya Nginden 1,3 JL. Panjang Jiwo 0,8 JL. Raya Kedung Baruk 0,9 JL. Raya Kalirungkut 0,9 JL. Raya Kalirungkut Kidul 2,1 JL. Raya Rungkut Tengah 0,4
JL. Raya Rungkut Menanggal 0,5 JL. Raya Taman Asri 0,8 JL. Arah Surabaya 1,4 Kampus 2 UIN Sunan Ampel Surabaya 0,7 Total 12,2 Tabel 4. Rute 4 Rute 4 Jarak JL. Jojoran 1 0 JL. Karang Menjangan 0,55 JL. Raya Menur 0,35 JL. Raya Menur Pumpungan 1,3 JL. Arief Rahman Hakim 1,2 JL. Dr. Ir. H. Soekarno 0,7 JL. Tol Waru Juanda 8 Kampus 2 UIN Sunan Ampel Surabaya 0,5 Total 12,6 Dibawah ini adalah Matrik Ketetanggaan dari semua rute:

## Gambar 3. Matrik Ketetanggaan
Dari hasil perhitungan di atas untuk urutan rute terpendek sampai terpanjang yaitu rute pertama dengan jarak tempuh 11,5 km, kemudian rute ketiga dengan jarak 12,2 km, lalu rute keempat dengan jarak 12,6 km, dan terakakhir rute kedua dengan jarak 15,1 km Hasil dari temuan diatas sesuai dengan penelitian terdahulu oleh Nava Gia Ginasta Mengenai penentuan rute terbaik, khususnya masalah pencarian rute terbaik mencari tempat parkir untuk menyimpan mobilnya. Pencarian Pertama Terbaik (BFS) diperbolehkan melakukan pencarian untuk mengunjungi node di tingkat yang lebih rendah. Ini adalah rute terbaik yang
dapat dipilih dengan menggunakan algoritma Dijkstra. Pencari tempat parkir telah dioptimalkan untuk
mengurangi waktu perjalanan dan arah tujuan, sebagaimana ditentukan oleh Algoritma Dijkstra. [8]. Kemudian sejalan dengan penelitian terdahulu oleh Jeprin Talunohi mengenai jalur terpendek yang dengan panjang lintasan 430,7 kilometer, yang dapat dilalui adalah AB-C-D-E-F-G-H-I-J-K-L. Berdasarkan hasil pengujian sistem yang dilakukan, rute Gunungsitoli menuju Pantai Hoya Gunungsitoli yang memiliki jarak 35,84 kilometer dan waktu tempuh 149,89 menit merupakan cara paling efisien bagi wisatawan untuk sampai ke lokasi pantai [9].
Kemudian sejalan dengan penelitian oleh Hendra digunakan dengan tujuan mengoptimalkan aspek-aspek tertentu, seperti konsumsi bahan bakar dan waktu perjalanan. Algoritme, salah satu komponen grafik, dapat digunakan untuk mencapai solusi ini. Dengan menggunakan Algoritma Dijkstra dan Algoritma Floyd-Warshall, jurnal ini dibuat untuk memberikan informasi kepada masyarakat umum. Hasil Algoritma Dijkstra lebih efisien dalam hal efisiensi perhitungan dan kompleksitas program berkat penelitian ini. Perhitungan kedua algoritma tersebut menghasilkan nilai bobot minimum yang sama dan akurat serta informasi rute terpendek yang dapat digunakan masyarakat untuk melakukan perjalanan lebih efisien di Surabaya. Dengan jarak 1,2 kilometer, perjalanan dari Stasiun Gubeng titik awal menuju Jalan Taman Apsari merupakan rute terpendek yang ditentukan dengan membandingkan kedua algoritma tersebut.

## Kesimpulan
Berdasarkan pembahasan sebelumnya, dapat disimpulkan bahwa telah berhasil menemukan jalur terpendek antara JL. Jojoran 1 dan Kampus 2 UIN Sunan Ampel Surabaya, yakni melalui rute pertama dengan jarak tempuh 11,5 km.
Meskipun jalur terpendek telah diidentifikasi, perlu diingat bahwa jalur terpendek tidak selalu berarti jalur tercepat. Berbagai faktor lingkungan seperti kemacetan, kondisi cuaca, kecelakaan, kondisi jalan yang buruk, dan faktor-faktor lainnya dapat mempengaruhi kecepatan perjalanan menuju tujuan, sehingga perlu dipertimbangkan dengan cermat dalam menentukan rute tercepat [10].

## Referensi
[1] D. Amir Sanjaya, “ Perencanaan Traffic Light Pada Simpang Jl.Purnama - Jl. M.Sohor-Jl. Letjen Sutoyo Kota Pontianak, ” J. Elektron. Laut, Sipil, dan Tambang, vol. 3, no. 3, pp. 1 – 13, 2016.
[2] A. Ghofur Wibowo and A. Purwo Wicaksono, “ Rancang Bangun Aplikasi untuk Menentukan Jalur Terpendek Rumah Sakit di Purbalingga dengan Metode Algoritma Dijkstra (An Application Design for Determining the Shortest Path of Hospital in Purbalingga Using Dijkstra Algorithm Method), ” Juita, vol. 1, p. 21,
2012.
[3] R. R. Al Hakim et al., “ Aplikasi Algoritma Dijkstra dalam Penyelesaian Berbagai Masalah, ” Expert J. Manaj. Sist. Inf. dan Teknol., vol. 11, no. 1, p. 42, 2021, doi:
10.36448/expert.v11i1.1939.
[4] M. Qomaruddin, M. T. Alawy, and dan S. Sugiono, “ Perancangan Aplikasi Penentu
Rute Terpendek Perjalanan Wisata di Kabupaten Jember Menggunakan Algoritma Dijkstra, ” Sci. Electro, vol. 6, no.
2, pp. 31 – 39, 2018
[5] M. Muharrom, “ Implementasi Algoritma Dijkstra Dalam Penentuan Jalur Terpendek Studi Kasus Jarak Tempat Kuliah Terdekat, ” Indonesian Jurnal Business Inteligence (IJUBI), vol. 3, no. 1, p. 25, 2020, doi: 10.21927/ijubi.v3i1.1229.
[6] N. Kusnia and R.N Darmawan, “ Penerapan Algoritmna Dijkstra untuk Menentukan Jalur Terpendek Jalur Lintas Darat dari AlunAlunKota Banyuwangi Menuju Alun Alun Kota Jember, ” Universitas PGRI
Banyuwangi, Vo. 1 No.2 pp. 22-30, 2017.
[7] L. Broumi, S., Bakal, A., Talea, M., Smarandache, F., & Vladareanu, “ Applying Dijkstra algorithm for solving neutrosophic shortest path problem, ” pp.412 – 416, 2016
[8] Ginasta, Nava Gia., Supriadi. “ Implementasi Pencarian Rute Terbaik untuk Mengetahui Lokasi Tempat Parkir pada sistem E- Parking Menggunakan Algoritma Dijkstra dan Best First Search ” , Vol. 4. No. 2, 2024. DOI
:
https://doi.org/10.57152/malcom.v4i2.126 1
[9] Talunohi, Jeprin. “ Implementasi Algoritma Dijkstra untuk Menentukan Rute Terpendek ke Wisata Pantai Pulau Nias ” , 2023 [10] Hendra., Yosefina Finsensia Riti. “ Perbandingan Agoritma Dijkstra dan Floydwarshall dalam Menentukan Rute Terpendek Stasiun Gubeng Menuju Wisata Surabaya. Universitas Muhammadiyah Tanggerang, Vol. 6 No. 3, 2022. DOI : htpp://dx.doi.org/10.31000/jika.v6i3.6528.