http://ejournal.uki.ac.id/index.php/edumatsains

## PENERAPAN ALGORITMA DIJKSTRA PADA PENDISTRIBUSIAN BAHAN BAKAR MINYAK DI PONTIANAK
Riski Apriadi * , Bayu Prihandono, Yundari
Jurusan Matematika FMIPA, Universtas Tanjungpura
Diterima: 28 Agustus 2022  Direvisi: 28 November 2022 Diterbitkan: 31 Januari 2023

## ABSTRACT
Determination of the shortest path or the fastest travel time is a problem that occurs to drivers of trucks loaded with fuel oil (BBM) when delivering their tanks to one of the public refueling stations (SPBU) in Pal Lima. To get to the destination, several paths that can be passed. This study aims to determine the shortest path and fastest travel time using Dijkstra's algorithm. Dijkstra's algorithm can be used on both directed and weighted graphs. The first step that must be done is to determine the starting node and destination node. After that, the calculation is carried out from the initial departure node to the neighboring node, the node with the smallest weight is used as the next calculation node. The same is done until all nodes are evaluated. Crossroads are assumed as vertices and between intersections as edges in Dijkstra's algorithm. From the results of the study, the shortest path was obtained through the Kapuas 2 Toll Road, Jl. Adi Sucipto, Jl. Imam Bonjol, Jl. Tanjung Pura, Jl. Rahadi, Jl. Mr. Love, Jl. Hassanudin, Jl. H. Rais, Pal III, Pal V with a minimum distance of 12,768 Km. For the fastest route, it is through the Kapuas 2 Toll Road, Jl. Major Alianyang, Jl. Arteri Supadio, Jl. General Ayani, Jl. Abdurrahman, Jl. Sultan Syahrir, Dr. Sutomo, Jl. Dr. Wahidin, Jl. Pal V with the fastest travel time of 27 minutes.
Keywords : Directed graphics, Fastest travel time, Shortest path.

## PENDAHULUAN
Penentuan  lintasan  terpendek  atau waktu  perjalanan tercepat  merupakan suatu permasalahan yang terjadi pada pengendara transportasi darat. Terdapat beberapa algoritma yang dapat membantu menentukan lintasan terpendek, diantaranya algoritma  greedy,  algoritma  Bellman-Ford dan algoritma Dijkstra (Hakim, Satria, Arief, Pangestu,  &  Jaenul,  2021).  Salah  satu contoh  yang  dapat  diaplikasikan  pada algoritma Dijkstra dalam kehidupan sehari- hari yaitu membantu menyelesaikan permasalahan  pada  perjalanan  truk  tangki muatan  BBM  dalam  menentukan  lintasan
terpendek atau lintasan tercepat (Anggraini & Mingparwoto, 2015).
Hal  yang  harus  diperhatikan  dalam menyalurkan  BBM  yaitu  waktu  tempuh perjalanan  dan  lintasan  yang  akan  dilalui. Salah  satu  kendala  dalam  penyaluran  BBM yaitu  banyaknya  lintasan  dari  Tol  Kapuas  2 menuju  SPBU  yang  berada  di  daerah Pontianak,  Kalimantan  Barat.  Penelitian dilakukan  dari  Tol  Kapuas  2,  dikarenakan pada  simpul  pengantar  (Depot)  menuju  Tol hanya memiliki satu lintasan saja dengan jarak tempuh  11.349  Km.  Persimpangan  jalan diasumsikan  sebagai  simpul  dan  antar persimpangan  sebagai  sisi,  serta  membentuk model  graf  berarah  maka  algoritma  Dijkstra
dapat  membantu  menentukan  lintasan terpendek  atau  waktu  perjalanan  tercepat (Ardana & Saputra, 2016).
Penelitian ini bertujuan untuk membantu  pengendara  dalam  menemukan lintasan  terpendek  dan  waktu  perjalanan tercepat pada lintasan yang dapat dilalui truk BBM, khususnya dari Tol Kapuas 2 menuju SPBU  di  Pal  Lima.  Data  yang  digunakan adalah  data  panjangnya  lintasan  (jalan), kecepatan  rata-rata  dengan  rumus  Gerak Lurus Beraturan (GLB) pada masing-masing jalan dan lamanya durasi waktu pada lampu merah.

## Teori Graf
Suatu  graf  berarah G merupakan himpunan pasangan terurut V ( G ) dan A ( G ),
dimana V ( G ) adalah himpunan tidak kosong dari simpul dan A ( G ) adalah himpunan busur
yang  menghubungkan  sepasang  simpul.
Dimisalkan a adalah busur yang menghubungkan  simpul u dan v ,  maka a dapat  ditulis  sebagai a =( u , v ).  Graf  berarah merupakan graf yang setiap sisinya memiliki orientasi arah, sisi pada graf berarah disebut busur.  Pada  graf  berarah,  ( u , v )  dan  ( v , u ) menyatakan dua busur yang berbeda dengan kata lain ( u , v )≠( v , u ) (Aziz, 2021).
Beberapa  faktor  yang  mempengaruhi penentuan  lintasan  terpendek  seperti  graf berbobot  dan  graf  berarah.  Graf  berbobot adalah  graf  yang  setiap  busurnya  diberi
sebuah  harga  (bobot).  Pemberian  bobot  pada setiap  busur  berbeda-beda  bergantung  pada permasalahan  yang  dimodelkan  dalam  graf. Bobot dapat menyatakan jarak antar dua buah kota,  waktu  tempuh  dari  sebuah  simpul menuju simpul yang lain (jaringan komputer), biaya perjalanan antar dua buah kota, ongkos produksi  dan  sebagainya  (Munir,  2005). Dalam  graf  berarah,  dua  simpul  yang  saling terhubung  bisa  dikatakan  bertetanggaan.  Hal ini  dikaji  dalam  Definisi  1.  Definisi  1  ini merupakan hal yang penting dalam pengerjaan algoritma Dijkstra.
Definisi 1: Dua buah simpul pada graf berarah
G dikatakan  bertetanggaan  bila  keduanya terhubung dan setiap simpul memiliki derajat masuk dan keluar. Pada graf berarah ( u , v ) dan ( v , u ) menyatakan dua busur yang berbeda.

## Algoritma Dijkstra
Dijkstra merupakan salah satu algoritma yang popular dalam membantu menyelesaikan permasalahan  pada  lintasan  terpendek  dalam graf berarah. Menurut Andrew Golbeng yaitu seorang  ahli  Microsoft  Research  Silicon Valley,  mengatakan  terdapat  banyaknya alasan mengapa pentingnya melakukan penelitian  dalam  mencari  lintasan  atau  jalan terpendek.  Lintasan  terpendek  merupakan masalah yang relevan untuk  berbagai  macam aplikasi  seperti  jaringan  rounting,  game  dan pemetaan  (Mohamad,  Ahmad,  &  Fernando,
2017). Adapun penyelesaian dalam
algoritma  Dijkstra  pada  penelitian  ini sebagai berikut (Harahap & Khairina, 2017). Pertama, menentukan simpul awal keberangkatan  dan  simpul  tujuan.  Kedua, membuat graf berarah pada setiap jalan yang dapat  dilalui.  Ketiga,  memberi  bobot  pada masing-masing sisi (jalan). Keempat, mengasumsikan  bahwa  kendaraan  selalu tepat  mengenai  lampu  merah  dan  hitung lamanya  waktu  perjalanan  pada  setiap  sisi (untuk  hitungan  waktu  perjalanan  tercepat)
menggunakan rumus:
      = v s t
dengan: t = waktu (jam), s = jarak (Km), dan v = kecepatan (Km/jam).
Kelima, tandai warna biru pada simpul keberangkatan,    lalu  hitung  jarak  pada simpul  yang  bertetangga  dengan    simpul awal.  Setelah  itu  beri  tanda  dalam  kurung hasil  hitungan  dan  nomor  simpul  yang didapatkan. Contoh jarak a menuju b sejauh 100m,  maka  diberi  tanda  (100  ( a ))  pada simpul b .  Keenam,  kemudian  beri  nilai  tak hingga  ( infinity )  pada  simpul  yang  tidak bertetanggaan.  Ketujuh,  jika  terdapat  dua simpul  yang  dilalui  maka  pertimbangkan nilai  terkecil  yang  telah  dihitung.  Bobot terkecil  dijadikan  simpul  keberangkatan selanjutnya.  Kedelapan,  beri  tanda  warna kuning  jika  terjadi  perubahan  lintasan, dimana  nilai  pada  lintasan  tersebut  lebih
kecil  dibandingkan  nilai  pada  lintasan  yang baru  dengan  tujuan  pada  simpul  yang  sama. Kesembilan,  beri  tanda  warna  orange  pada simpul  yang  mengalami  penambahan  waktu lampu  merah  (berlaku  untuk  hitungan kecepatan waktu tempuh). Kesepuluh, pastikan  semua  simpul  sudah  terlewati. Kesebelas,  setelah  semuanya  sudah  terlewati maka lintasan terpendek dan waktu perjalanan tercepat  ditemukan  dengan  melihat  dari simpul tujuan sampai ke simpul awal.

## METODE PENELITIAN
Metode penelitian ini dilakukan dengan 2  cara  yaitu  studi  literatur  dan  wawancara.
Studi  literatur  (kajian  teori)  diperoleh  dari beberapa buku dan artikel yang terkait sebagai landasan  teori  mengenai  teori  graf  secara umum  dan  fokus  ke  teori  yang  mempelajari dalam menentukan lintasan terpendek.
Sedangkan  hasil  wawancara  dilakukan  untuk mendapatkan  data  yang  dibutuhkan  dalam penelitian  seperti  data  ukuran  jalan,  rata-rata kecepatan  kendaraan  pada  masing-masing jalan,  dan  durasi  waktu  pada  lampu  merah. Flowchart algoritma Dijkstra pada Gambar 1.

## HASIL DAN PEMBAHASAN
Dalam pendistribusian BBM banyaknya pangkalan  SPBU  yang  menjadi  titik  tujuan supir  truk  tangki  BBM  yang  berada  di Pontianak Kalimantan Barat. Terdapat beberapa lintasan yang dapat dilalui.
Gambar 1. Flowchart Algoritma Dijkstra
Lintasan  yang  dapat  dilalui  truk tersebut  diantaranya  yaitu,  Jl.  Pak  Kasih, Rahadi  Usman, Tanjung  Pura, Imam Bonjol dan lain sebagainya seperti pada Gambar 2.
Gambar 2. Lokasi Penelitian
Dengan mengasumsikan simpul
merah  pada  Gambar  2  sebagai  simpul keberangkatan  dan  bendera  merah  sebagai simpul tujuan serta menjadikan penghubung
antar simpang jalan sebagai simpul dan jalan sebagai sisi, maka peta dapat dibentuk dalam sebuah  graf  berarah  yang  direpresentasikan pada Gambar 3.
Simpul Start Simpul Tujuan Persimpangan Jalan Jalan antar persimpangan
Gambar 3 . Pengkonstruksian Masalah dalam Graf
Berdasarkan  Gambar  3,  diperoleh model matematika sebagai berikut.

## 1. Variabel keputusan
Variable keputusan merupakan
variable yang mempengaruhi nilai tujuan yang  ingin  dicapai.  Pada  penelitian  ini yang  menjadi  variable  keputusan  yaitu ada  atau  tidak  adanya  perjalanan  dari simpul i ke simpul j .
   =
j i j i X ij ke perjalanan ada tidak jika , 0 ke perjalanan ada jika , 1

## 2. Fungsi tujuan
Tujuan  dari  penelitian  ini  adalah menentukan  lintasan  terpendek  dan waktu perjalanan tercepat,
a. Lintasan Terpendek ( Z min )
( )  − = = = 1 0 1 min n i n j ij ij X C Z (1)
b. Lintasan Tercepat ( F min ) ( )  − = = = 1 0 1 min n i n j ij ij W C F (2)
Dengan:
C ij =  Bobot  (jarak)  yang  terhubung
( i , j ) W ij = Bobot (waktu) yang terhubung
( i , j )
3. Fungsi Kendala
Fungsi  kendala  merupakan  pembatas terhadap variable keputusan.
a. Kendaraan  yang  mengunjungi  satu titik akan meninggalkan titik tersebut.
0 1 1 0 =   = − = n j ji n i ij X X
b. Harus  ada  satu  busur  yang  keluar
dari simpul x (simpul start).
 = = n j xj X 1 1
c. Harus  ada  satu  busur  yang  masuk
dari simpul y (simpul tujuan).
 − = = 1 0 1 n i iy X

## Data Penelitian
Data panjangnya lintasan dan kecepatan rata-rata  kendaraan  diperoleh  dari  Dinas Perhubungan  Kota  Pontianak  dan  hasil wawancara.  Dengan  menjadikan  simpul sebagai  penghubung  antar  simpang  jalan  dan sisi  sebagai  jalan,  maka  diperoleh  hasil panjang lintasan dan waktu tempuh kendaraan dari simpul ke simpul seperti Tabel 1.
Tabel 1. Ukuran jalan dan Waktu Tempuh Perjalanan Jalan/Sisi (X) Bobot (meter) ( C ij ) Nama Jalan Kecepaan Rata-Rata (Km/Jam) Durasi Perjalanan (menit) ( W ij ) i j 1 2 1.000 Tol Kapuas II 30 2 2 3 1.463 Major Alianyang 40 2,2 2 4 3.288 Adi Sucipto 40 5 3 5 3.427 Arteri Supadio 50 4,2 4 5 1.000 Daya Nasional 30 2 4 6 1.232 Imam Bonjol 30 2,5 5 8 451 Jendral Ayani (I) 50 0,6 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 43 44 667 Tabrani Ahmad (II) 40 1
Berdasarkan  Tabel  1  diperoleh  jarak terpanjang  yaitu  pada  jalan  Ateri  Supadio dengan panjang 3.427 meter. Pada penelitian ini simpul no 1 pada Gambar 3 melambangkan simpul awal perhitungan dan simpul  no  44  merupakan  simpul  tujuan. Dalam melakukan perhitungan waktu perjalanan tercepat, ada beberapa faktor yang menjadi  pertimbangan  dalam  perhitungan yaitu,  adanya  penumpukan  arus  lalu  lintas, kecepatan  rata-rata  kendaraan  pada  masing-
masing jalan dan lamanya durasi waktu pada lampu  merah.  Diasumsikan  jika  truk  tangki tiap mengenai  lampu merah hanya terhitung satu kali putaran waktu. Jalur kiri pada lampu merah  untuk  beberapa  jalan  akan  diabaikan seperti  (Jl.  Jendral  Ayani,  Jl.  M.Sohor,  Jl. Imam  Bonjol,  Jl.  Tanjung  Pura,  Jl.  Gajah Mada,  Jl.  Gusti  Hamzah  dan  Jl.  Khw. Hasyim).  Durasi  lampu  merah  dapat  dilihat pada Tabel 2.
Perhitungan Lintasan Terpendek

## Menggunakan Algoritma Dijkstra
Dalam  perhitungan  jarak  terpendek perjalanan truk tangki, lamanya durasi lampu
merah  akan  diabaikan.  Pada  perhitungan kecepatan  waktu  tempuh,  durasi  lampu merah  dan  kecepatan  maksimal  kendaraan pada setiap jalan di pertimbangkan.
Tabel 2. Durasi Lampu Merah Simpul Lampu Merah Jalan/Sisi (X) Durasi Lampu (detik) Waktu (Menit) i j 5 3 5 65 1,1 4 5 80 1,4 6 4 6 100 1,7 14 6 14 80 1,4 15 10 15 95 1,6 14 15 95 1,6 17 11 17 80 1,4 16 17 80 1,4
⋮
37 ⋮ 36 ⋮ 37 ⋮ 95 ⋮ 1,6 Langkah awal dalam perhitungan yaitu menghitung panjang lintasan yang
bertetanggaan  dengan  simpul  1  yaitu  pada simpul 2. Kemudian bobot terkecil didapatkan  pada  simpul  2  yang  akan dijadikan simpul keberangkatan selanjutnya.
Tabel 3. Perhitungan Lintasan Terpendek Algoritma Dijkstra Simp ul Lintasan Bobot pada lintasan 1 2 3 4 5 ⋯ 40 41 42 43 44 1 1 0 1.00 0
∞ ∞ ∞ ⋯ ∞ ∞ ∞ ∞ ∞ 2 1,2 0 1.00 0 2.46 3 5.89 0 ∞ ⋯ ∞ ∞ ∞ ∞ ∞ 3 1,3 0 1.00 0 2.46 3 5.28 8 5.52 0 ⋯ ∞ ∞
∞ ∞ ∞ 4 1,2,4 0 1.00 0 2.46 3 5.28 8 5.52 0
⋯ ∞ ∞
∞ ∞ ∞ 5 1,2,4,5 0 1.00 0 2.46 3 5.28 8 5.52 0
⋯ ∞ ∞ ∞ ∞ ∞ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 40 1,2,4,6,14,27,39,40 0 1.00 0 2.46 3 5.28 8 5.52 0 ⋯ 12.65 2 12.05 6 13.06 9 14.63 9 12.76 8 44 1,2,4,6,14,27,33,34,35,36, 41,44 0 1.00 0 2.46 3 5.28 8 5.52 0 ⋯ 12.65 2 12.05 6 13.06 9 14.63 9 12.76 8 42 1,2,4,6,14,27,33,39,44 0 1.00 0 2.46 3 5.28 8 5.52 0 ⋯ 12.65 2 12.05 6 13.06 9 14.63 9 12.76 8 43 1,2,4,6,14,27,33,39,40,43 0 1.00 0 2.46 3 5.28 8 5.52 0 ⋯ 12.65 2 12.05 6 13.06 9 14.63 9 12.76 8 38 1,2,4,5,8,11,12,13,21,32,3 8 0 1.00 0 2.46 3 5.28 8 5.52 0 ⋯ 12.65 2 12.05 6 13.06 9 14.63 9 12.76 8
Hitung panjang lintasan yang bertetanggaan  dengan  simpul  2  yaitu  pada simpul  3  dan  4  dengan  menjumlahkan panjang  lintasan  dari  simpul  1.  Dari  hasil perhitungan  diperoleh  lintasan  terpendek sementara yang memiliki bobot terkecil yaitu pada simpul  3 melalui lintasan 1, 2, 3 maka simpul 3 dijadikan keberangkatan selanjutnya. Hitung jarak yang bertetanggaan
dengan simpul 3 yaitu pada simpul 5 dengan menjumlahkan panjang lintasan dari simpul 1 menuju  simpul  5  yang  melewati  simpul  3. Lakukan  hal  yang  sama  hingga  semua  titik terlewati, dapat dilihat seperti pada Tabel 3.
Dari  hasil  perhitungan  pada  Tabel  3 diperoleh  lintasan  terpendek  yaitu  12.768 meter  sehingga  perhitungan  tersebut  dapat dibentuk dalam graf pada Gambar 4.
Gambar 4. Lintasan terpendek Algoritma Dijkstra
Gambar 4 merupakan hasil perhitungan algoritma  Dijkstra.  Perhitungan  dilakukan seperti  langkah  pada  Tabel  3  untuk memperoleh  lintasan  terpendek  dengan memastikan  bahwa  semua  simpul  sudah tereliminasi.  Hasil  perhitungan  lintasan terpendek yaitu melalui simpul 1, 2, 4, 6, 14,
27, 33, 34, 35, 36, 37, 41, 44 pada Gambar 4.
Pada Gambar 3
didapatkan
𝑋 12 , 𝑋 24 , 𝑋 46 , 𝑋 614 , 𝑋 1427 , 𝑋 2733 , 𝑋 3334 , 𝑋 3435 , 𝑋 3536 , 𝑋 3637 , 𝑋 3741 , 𝑋 4144 = 1 sedangkan variabel keputusan yang lain 0. Berdasarkan Persamaan  (1)  diperoleh  lintasan  terpendek ( Z min ) adalah sebagai berikut.
 = = = 43 1 44 2 min i j ij ij X C Z
) 386 ( ) 982 ( ) 262 ( ) 413 ( ) 690 ( ) 766 ( ) 714 . 1 ( ) 232 . 1 ( ) 288 . 3 ( ) 000 . 1 ( min + + + + + + + + + = Z meter 768 . 12 min = Z

## Perhitungan Lintasan Tercepat Algoritma

## Dijkstra
Dalam  perhitungan  waktu  tercepat perjalanan truk tangki, lamanya durasi lampu merah  dan  kecepatan  maksimal  kendaraan pada  setiap  jalan  akan  dipertimbangkan. Tanda  warna  merah  pada  Gambar  5 melambangkan  adanya  lampu  merah  dan diasumsikan perjalanan truk akan selalu tepat mengenai lampu merah.
Pada  Tabel  4  langkah  awal  dalam perhitungan  yaitu  menghitung  panjang
lintasan yang bertetanggaan dengan simpul 1 yaitu  pada  simpul  2.  Kemudian  simpul dengan  bobot  terkecil  didapatkan  pada simpul  2  yang  akan  dijadikan  simpul Perhitungan  selanjutnya.  Hitung  panjang lintasan yang bertetanggaan dengan simpul 2 yaitu  pada  simpul  3  dan  4  dengan menjumlahkan  panjang  lintasan  dari  simpul 1. Lakukan hal yang sama hingga semua titik tereliminasi.
Tabel 4. Perhitungan Lintasan Tercepat Algoritma Dijkstra V  Lintasan 1  2 3 4 5 ⋯ 40 41 42 43 44 1  1 0 2 ∞ ∞ ∞ ⋯ ∞ ∞ ∞ ∞ ∞ 2  1,2 0 2  5, 8 8, 6 ∞ ⋯ ∞ ∞ ∞ ∞ ∞ 3  1,3 0 2  5, 8 8, 6 1 0 ⋯ ∞ ∞ ∞ ∞ ∞ 4  1,2,4 0 2  5, 8 8, 6 1 0 ⋯ ∞ ∞ ∞ ∞ ∞ 5  1,2,3,5 0 2  5, 8 8, 6 1 0 ⋯ ∞ ∞ ∞ ∞ ∞ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 4 0 1,2,4,6,14,27,33,39,40 0 2  5, 8 8, 6 1 0 ⋯ 25, 7 25, 8 25, 8 28, 7 28, 2 4 1 1,2,3,5,8,11,17,18,19,20,31,4 1 0 2  5, 8 8, 6 1 0 ⋯ 25, 7 25, 8 25, 8 28, 7 28, 2 4 2 1,2,4,6,14,27,33,39,42 0 2  5, 8 8, 6 1 0 ⋯ 25, 7 25, 8 25, 8 28, 7 26, 9 4 4 1,2,3,5,8,11,17,18,19,20,31,4 1,44 0 2  5, 8 8, 6 1 0 ⋯ 25, 7 25, 8 25, 8 28, 7 26, 9 4 3 1.2,4,6,14,27,33,39,40,43 0 2  5, 8 8, 6 1 0 ⋯ 25, 7 25, 8 25, 8 28, 7 26, 9
Dari  hasil  perhitungan  pada  Tabel  4 diperoleh  lintasan  terpendek  yaitu  12.768 meter  sehingga  perhitungan  dapat  dibentuk dalam graf pada Gambar 6.
Gambar 5. Graf Berarah Pada Lampu
Merah Gambar 6. Lintasan Tercepat Algoritma Dijkstra
Pada  Gambar  6  merupakan  hasil perhitungan  lintasan  tercepat  algoritma
Dijkstra.  Perhitungan  dilakukan  seperti langkah  pada  Tabel  4  untuk  memperoleh lintasan  tercepat  dengan  memastikan  bahwa semua  simpul  sudah  tereliminasi.  Hasil perhitungan  lintasan  tercepat  yaitu  melalui simpul 1, 2, 3, 5, 8, 10, 17, 18, 19, 20, 31, 43, 44.  Pada  Gambar  6  diperoleh  lintasan 𝑋 1,2 ,
𝑋 2,3 , 𝑋 3,5 , 𝑋 5,8 , 𝑋 8,11 , 𝑋 11,17 , 𝑋 17,18 , 𝑋 18,19 ,
𝑋 19,20 , 𝑋 20,31 , 𝑋 31,41 , 𝑋 41,44 =  1.  sedangkan variabel keputusan yang lain 0. Berdasarkan Persamaan  (2)  diperoleh  lintasan  tercepat
(𝐹 min⁡ ) adalah sebagai berikut.
𝐹 𝑚𝑖𝑛 = ∑ ∑ 𝐶 𝑖𝑗 𝑋 𝑖𝑗 44 𝑗=2 43 𝑖=1
𝐹 𝑚𝑖𝑛 = (2) + (2,2) + (4,2) + (0,55) +
(0,8) + (3) + (0,9) + (1) + (1,3) +
(1,5) + (3,4) + (1,1)
𝐹 𝑚𝑖𝑛 = 20,95 menit
𝐹 𝑚𝑖𝑛 ⁡𝑡𝑜𝑡𝑎𝑙 = 𝐹 𝑚𝑖𝑛 + Durasi  lampu  merah yang dilalui
𝐹 𝑚𝑖𝑛 ⁡𝑡𝑜𝑡𝑎𝑙 = 20,95 + 5,95 = 26,9 menit ≈ 27 menit

## KESIMPULAN
Dalam menenentukan lintasan terpendek  dan  lintasan  tercepat  dari  satu simpul  ke  simpul  yang  lain  menggunakan algoritma  Dijkstra,  data  yang  diperlukan yaitu  data  jalan,  ukuran  jalan,  durasi  lampu merah  dan  kecepataan  rata-rata  kendaraan pada masing masing jalan. Dengan menjadikan  persimpangan  jalan  sebagai simpul  dan  penghubung  jalan  sebagai  sisi sehingga membentuk sebuah graf. Dari hasil penelitian diperoleh lintasan terpendek yaitu melalui jalan Tol Kapuas 2, Jl. Adi Sucipto, Jl. Imam Bonjol, Jl. Tanjung Pura, Jl. Rahadi, Jl. Pak Kasih, Jl. Hassanudin, Jl. H.Rais, Pal
III, Pal V dengan jarak tempuh paling pendek
12,768  Km.  Untuk  Lintasan  perjalanan tercepat  yaitu melalui simpul  Tol  Kapuas 2,
Major  Alianyang,  Ateri  Supadio,  Jendral Ayani,  Abdurrahman,  S.  Syahrir,  Dr.
Sutomo,  Dr.  Wahidin,  Pal  V  dengan  jarak tempuh  paling  cepat  27  menit  dengan  rata- rata kecepatan pada Lintasan yang dilalui 43 km/jam.

## DAFTAR PUSTAKA
Anggraini,  F.,  &  Mingparwoto,  S.  (2015).
Penerapan Metode Algoritma Bellmann-Ford dalam Aplikasi Pencarian Lokasi  Perseroan Terbatas di  PT.  Jakarta  Industrial  Estate
Pulogadung. Jurnal Teknologi , 28-34. Ardana, D., & Saputra, R. (2016). Penerapan
Algoritma  Dijkstra  pada  Aplikasi Pencarian Lintasan Bus Trans
Semarang. Seminar  Nasional  Ilmu
Komputer (SNIK) , (pp. 299-306).
Aziz, A. T. (2021). Eksplorasi Justifikasi dan
Rasionalisasi Mahasiswa dalam Konsep Teori Graf. Jurnal Pendidikan Matematika Raflesia , 40-
54.
Hakim,  R.  A.,  Satria,  M.  H.,  Arief,  Y.  Z.,
Pangestu,  A.,  &  Jaenul,  A.  (2021). Penggunaan Algoritma Dijkstra
untuk berbagi masalah.
Harahap,  M.  K.,  &  Khairina,  N.  (2017).
Pencarian  Jalur  Terpendek  dengan
Algoritma  Dijkstra. Sinkron:  Jurnal dan  Penelitian  Teknik  Informatika , 18-23. Mohamad,  M.,  Ahmad,  I.,  &  Fernando,  Y.
(2017).  Pemetaan  Potensi  Pariwisata Kabupaten  Waykanan  menggunakan Algoritma Dijkstra. Jurnal Komputer
Terapan , 169-178. Munir,  R.  d.  (2005). Matematika  Diskrit. Bandung: Informatika.