## PENENTUAN ALUR TERPENDEK PENGIRIMAN BARANG PT.KENCANA LINK NUSANTARA MEDAN DENGAN ALGORITMA DJIKSTRA

## Ahmad Zuhri Hasibuan
Mahasiswa Teknik Informatika STMIK Budi Darma Medan Jl. Sisingamangaraja No.338 Simpang Limun Medan

## ABSTRAK
Penentuan  jalur  terpendek  merupakan  bagian  pencarian  jalur  dengan    jarak  paling  minimum.  Algoritma  djikstra  adalah algoritma  yang  paling  terkenal  dalam  pencarian  jalur  terpendek.  Algoritma  Djikstra  merupakan  salah  satu  algoritma pencarian  jalur  terpendek  yang  paling  efesien  dibandingkan  algoritma  lain.  Algoritma  dijkstrsa  mencari  satu  titik  yang jumlah bobotnya lebih kecil. Pada skiripsi ini, penulis melakukan suatu penerapan algoritma Djikstra pada  penentuan jalur terpendek dengan menggunakan graf berbobot untuk menghasilkan jalur terpendek yang dilalui pada pengantaran barang PT.Kencana  Link  Nusantara  Medan.Perhitungan  akan  dilakukan  dengan  algoritma  djikstra    dengan  menghitung  bobot terkecil  dari  titik  awal  ke  titik  tujuan.  Algoritma  Djikstra  diterapkan  pada  pengantaran  barang  yang  dilakukan  di  kota Medan  dari  Jl.  Panglima  Denai  Menuju  Jl.Krakatau.  Hasil  perhitungan  akan  diterapkan  kedalam  perangkat  lunak. Perancangan  sisitem  dilakukan  dengan  beberapa  tahapan,  yaitu  pembuatan  use  case  diagram,  Activity  diagram  dan rancangan antar muka
Kata Kunci : Penentuan Jalur terpendek, Graf Berarah, Simpul Graf, Matriks Ketetanggaan

## I. PENDAHULUAN
PT. Kencana Link Nusantara Medan merupakan  perusahan yang bergerak  dibidang pengiriman  barang.  Petugas  pengiriman  barang pastinya  menginginkan  jalur  yang  paling  efesien dalam  menepuh  tujuan  yang  ditempuh.  Pengiriman barang  yang  dilakukan  menimbulkan  beberapa masalah  untuk  melakukan  pengantaran  barang  yaitu adanya beberapa rute yang bisa ditempuh.
Algoritma  Djikstra  menurut  penemunya seorang  ilmuwan  komputer  Edager  Djikstra  adalah sebuah  algoritma  rakus    yang  dipakai  untuk memecahkan masalah dalam penentuan jalur terpendek.  Persoalan  ini  sering  diimplementasikan dengan  bentuk graph .  Teori graph merupakan  pokok bahasan  yang  usianya  sudah  tua,  namun  memiliki banyak  tarapan  sampai  saat  ini. Graph digunakan untuk  mempersentasekan diskrit dan  hubungan antara objek-objek  tersebut.  Representasi  visual  dari graph adalah  dengan  menyatakan  objek  dinyatakan  sebagai bulatan atan. Dengan menggunakan Aplikasi Penentuan  Rute  Terpendek  Menggunakan  Algoritma Dijkstra  sehingga  aplikasi  tersebut  layak  untuk digunakan. Namun hal  itu tergantung pada persoalan- persoalan yang dihadapi.

## II. TEORITIS

## A. Graf
Secara  matematis  Graf  didefenisikan  sebagai pasangan himpunan (v, e) di tulis dengan notasi G=(V, E) yang  dalam  hal  ini V adalah  himpumam  tidak kosong  dari  simpul-simpul  ( vertices dan node )  dan E adalah  himpunan  sisi  ( edges atau arcs )  yang menghubungkan sepasang simpul. Jadi defenisi diatas menyatakan bahwa V tidak  boleh kosong , sedangkan E boleh  kosong.  Suatu  graf  dimungkinkan  tidak mempunyai  sisi satu buahpun, tetepi  simpulnya  harus ada,  minimal  satu.  (Rinaldi  Munir,  Matematika Diskrit, 2010 : 356) .
Simpul  pada  graf  dapat  dinomori  dengan  huruf, seperti a, b, c.... v, w...., dengan bilangan asli 1, 2, 3, ...,
atau  gabungan  keduanya.  Sedangkan  sisi  yang menghubungkan simpul u dengan simpul v dinyatakan dengan  pasangan  ( u , v )  atau  dinyatakan  dengan lambang e 1 , e 2 ,...  dengan  kata  lain,  jika  e  adalah  sisi yang menghubungkan simpul u dengan simpul v maka e dapat ditulis dengan e = (v, v).Secara geometris graf digambarkan  sebagi  sekumpulan  noktah  (simpul) didalam  bidang  dwimatra  yang  dihubungkan  dengan sekumpulan garis (sisi) (Rinaldi Munir, 2010).

## B. Algoritma Djikstra
Algoritma  Djikstra  yang  ditemukan  oleh Djikstraa  untuk  mencari  path  terpendek  merupakan algoritma yang lebih efesien. Dibandingkan algoritma wharshall,  meskipun  implementasinya  juga  lebih sukar. Misalkan G adalah graf berarah berlebel dengan titik-titik V ( G )= { v 1 , v 2 ...,v n }dan path terpendek yang dicari adalah dari v 1 ke v n . Algoritma Djikstra dimulai dari titik v 1 . Dalam iterasinya, algoritma akan mencari satu titik  yang  jumlah  bobotnya dari 1 terkecil. Titik- titik  yang  terpilih  dipisahkan,  dan  titik-titik  tersebut tidak diperhatikan lagi dalam iteras berikutnya.
Misalkan:
V ( G ) = { v 1 ,v 2 ,...v n }. L =  Himpunan  titik-titk ∈ V ( G )  yang  sudah terpilih dalam jalur path terpende D ( j ) = Jumlah bobot path terkecil v 1 ke v 2 . W ( i, j ) = Bobot garis dari titik v 1 ke titik v j . W* ( 1, j )   = Jumlah bobot path terkecil dari v 1 ke v j .
Secara  formal,  algoritma  Djikstra  untuk mencari path terpendek adalah sebagai berikut:
1. L = {  }; V = { v 2 , v 3 ,...,v n }. 2. Untuk i = 2, ..., n , lakukan D ( i ) = W ( 1,i )
3. Selama vn ∈ L lakukan :
a. Pilih titik vk ∈ V-L dengan D ( k ) terkecil L = L ∪ { v k }
b. Untuk setiap vj ∈ V - L lakukan :
Jika D ( j ) > D ( k ) + W ( k j ) maka ganti D ( j ) dengan D ( k ) + W ( k,j ) 4. Untuk setiap v j ∈ V , w* ( 1,j ) = D ( j )

## III. ANALISA DAN PERANCANGAN
Pencarian rute terpendek adalah suatu pencarian    rute  dari  suatu  jalur  ke  jalur  lainya    untuk meminimaliasi jarak pada suatu lintasan tertentu yang saling  berhubungan.    Persoalan  lintasan  terpendek  ini sering dilakukan dalam graf dan merupakan salah satu masalah  optimasi.  Dalam  pencarian  jalur  terpendek dengan  menggunakan  graf  berbobot.  Asumsi  pada penentuan  jalur  terpendek  ini  bahwa  setiap  bobot bernilai  positip.  Lintasan  terpendek  sering  dipakai untuk  pencarian  jarak  antar  suatu  kota  dalam  kasus pengiriman  barang  agar  menghasilkan  jarak  yang minimum  sehingga  dapat  menghemat  biaya  yang dikeluarkan dalam melakukan pengiriman barang.
Algoritma  Djikstra membutuhkan  prameter tempat  asal,  dan  tempat  tujuan.  Hasil  akhir  dari algoritma  ini  adalah  jarak  terpendek  dari  tempat  asal ke  tempat  tujuan  beserta  jalur  terpendek  yang  akan dilalui.
Adapun  langkah-langkah  penyelesaian  pada algoritma Djikstra adalah sebagai berikut:
1. Beri  nilai  bobot  (jarak)  untuk  setiap  titik  ke  titik lainnya, lalu  beri nilai 0 pada node awal atua titik keberangkatan dan nilai tak hingga terhadap node lain (belum terisi)
2. Atur  semua  node  belum  terjamah  dan  atur  node awal sebagai node keberangkatan.
3. Dari  node  keberangkatan,  pertimbangkan  node tetangga  yang  belum  terjamah  dan  hitung jaraknya dari titik keberangkatan.
4. Saat  kita  selesai  mempertimbangkan  setiap  jarak terhadap  node  tetangga,  tandai  node  yang  telah terjamah  sebagai  node  terjamah.  Node  terjamah tidak  akan  pernah  di  cek  kembali,  jarak  yang disimpan  adalah  jarak  terakhir  dan  yang  paling minimal bobotnya.
5. Atur  node  belum  terjamah  dengan  jarak  terkecil (dari node keberangkatan) sebagai node Keberangkatan  selanjutnya  dan  lanjutkan  dengan kembali ke step 3
Gambar 1 : Graf Penentuan Jalur terpendek
Mula-mula L= {} dan Untuk i= 2....,n; lakukan D (i) = w (1,i) V={v2,v3,v4,v5,v6,v7,v8} Pilih titik vk dengan d(k) terkecil

## Lakukan vj ε V-L
D(j) >  D (k) + W (k,j) maka ganti D(j) dengan D (k)
+ W(k,j) V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 1 ∞ 3 5 ∞ ∞ ∞ ∞ ∞ V 2 ∞ ∞ ∞ 8 8 ∞ ∞ ∞ V 3 ∞ 2 ∞ 8 ∞ ∞ ∞ ∞ V 4 ∞ ∞ ∞ ∞ ∞ 2 6 ∞ V 5 ∞ ∞ 4 12  ∞ 11 6 ∞
V 6 ∞ ∞ ∞ ∞ ∞ ∞ 5 2 V 7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 V 8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
V1- V2 - V5 - V4 - V6 - V8 =27
V1- V2 - V4 - V6  V8  =15 V1- V2 - V4 - V7 - V8 = 21 V1 - V2 - V5 - V4 – V6 – V7- V8 = 232
V1 - V2 - V5 - V6 - V8 = 24 V1 – V3 – V4 - V6 - V8 = 17 V1  - V3 -  V2 – V4 – V6  - V7 -  V8 = 24 Iterasi 1 D2 = w (1, 2) = 3 D3 = w (1, 3) =5 D4 = w (1, 4) = ∞ D5 = w (1, 5) = ∞ D6 = w (1, 6) = ∞ D7 = w (1, 7) = ∞
D8 = w (1, 8) = ∞ Iterasi 2
Vn=  v8    ε    L  sehinga  langkah  berikut  berikutnya dilakukan
D(k) terkecil adalah D(2) sehingga Vk = v2. V-L ={v2, v3, v4, v5, v6,v7,v8}-{v2}=v2 Untuk j = 3 D (j) = D (3)= 5 ; D (k) + W (k, j) = D (2) + W (2, 3) = 3 + ∞ = ∞ Oleh  karena  D  (3)  >  D  (2)  maka  harga  D  (3)  adalah tetap =5 Untuk j = 4 D (j) = D (4) = ∞; D (k) + W (k, j) = D (2) + W (2, 4) = 3 + 8 = 11 Oleh karena D (4) > D (2) maka harga D (4) menjadi =11 Untuk j = 5 D (j) = D (5) = ∞; D (k) + W (k, j) = D (2) + W (2, 5) = 3 + 8 = 11
Oleh karena D (5) > D (2) maka harga D (5) menjadi = 11 Untuk j = 6 D (j) = D (6) = ∞; D (k) + W (k, j) = D (2) + W (2, 6) = 3 + ∞  = ∞
W =
Oleh  karena  D  (6)  >  D  (2)  maka  harga  D  (6)  adalah tetap = ∞ Untuk j = 7 D (j) = D (7) = ∞; D (k) + W (k, j) = D (2) + W (2, 7) = 3+ ∞  = ∞ Oleh  karena  D  (7)  >  D  (2)  maka  harga  D  (7)  adalah tetap = ∞ Untuk j = 8 D (j) = D (8) = ∞; D (k) + W (k, j) = D (2) + W (2, 8) = 3 + ∞  = ∞ Oleh  karena  D  (8)  >  D  (2)  maka  harga  D  (8)  adalah tetap = ∞ Iterasi ke 3 Vn=  v8    ε  L  sehinga  langkah  berikut  berikutnya dilakukan Lakukan langkah diatas kembali D (k) terkecil adalah D(4) sehingga vk = v4
V-L(v2,v3,v4,v5,v6,v7,v8}-{v2,v4}=
{v3,v5,v6.v7.v8} Untuk j = 3
D (j) = D (3) = 5; D (k) + W (k, j) = D (4) + W (4, 3) = 11+ ∞ = 11 Oleh karena D (3) > D (4) maka harga D (3) menjadi = 5 Untuk j = 4 D (j) = D (4) = 11; D (k) + W (k, j) = D (4) + W (4, 4) = 11 + ∞  = 11
Oleh karena D (4) > D (4) maka harga D (4) menjadi = 11 Untuk j = 5
D (j) = D (5) = 11; D (k) + W (k, j) = D (5) + W (4, 5) = 11 + ∞ = ∞
Oleh  karena  D  (5)  >  D  (4)  maka  harga  D  (5)  adalah tetap = 11 Untuk j = 6
D (j) = D (6) = ∞; D (k) + W (k, j) = D (4) + W (4, 6) = 11 + 2 = 13 Oleh karena D (6) > D (4) maka harga D (6) menjadi = 13
Untuk j = 7 D (j) = D (7) = ∞; D (k) + W (k, j) = D (4) + W (4, 7)
= 11 + 6 = 17
Oleh karena D (7) > D (4) maka harga D (7) menjadi = 17 Untuk j = 8 D (j) = D (8) = ∞; D (k) + W (k, j) = D (4) + W (4, 8) = 11+ ∞  = ∞ Oleh karena D (8) > D (5) maka harga D (8) tetap = ∞ Iterasi ke 4
Vn= v8 ε  L sehinga ulangi langkah diatas
D(k) terkecil adalah D(6) sehingga vk =v6
V-L = {v2,v3,v4,v5,v6,v7,v8}- {v2,v4,v6}={v3,v5.v7.v8} Untuk j = 3 D (j) = D (3) = 5 ; D (k) + W (k, j) = D (6) + W (6, 3) = 13 + ∞ = ∞ Oleh karena D (3) > D (6) maka harga D (3) tetap =5 Untuk j = 4 D (j) = D (4) = 11 ; D (k) + W (k, j) = D (6) + W (6, 4) = 13 + ∞ = ∞
Oleh karena D (4) > D (6) maka harga D (4) tetap =11
Untuk j = 5 D (j) = D (5) = 11 ; D (k) + W (k, j) = D (6) + W (6, 5) = 13 + ∞ = ∞ Oleh  karena  D  (5)  >  D  (6)  maka  harga  D  (5) tetap  = 11
Untuk j = 6
D (j) = D (6) = 13 ; D (k) + W (k, j) = D (6) + W (6, 6) = 13 + ∞ = ∞ Oleh  karena  D  (6)  >  D  (6)  maka  harga  D  (6) tetap  = 13
Untuk j = 7
D (j) = D (7) = 17 ; D (k) + W (k, j) = D (6) + W (6, 7)
= 13 + 5 = 18 Oleh karena D (7) > D (6) maka  harga D (7) menjadi = 18 Untuk j = 8 D (j) = D (8) = ∞ ; D (k) + W (k, j) = D (6) + W (6, 8) = 13 + 2= 15
Oleh  karena  D  (8)  >  D  (6)  maka  harga  D  (8) tetap  = 15
Vn  =  V8  ε  L,  maka  perhitungan  dihentikan,    jalur terpendek  yang  dilalui  pada  graf  dari  v1  menuju  v8 adalah  15  dengan  perhitungan  jalur  yang  dibaca mundur  pada  hasil  matriks  di  bawah  adalah  sebagai berikut:
1. Pada titik terakhir yaitu  v8 diperoleh penurunan jarak  dari  tak  terhingga  menjadi  15  maka  titik yang  akan  dijadikan  jalur  terpendek  adalah  titik pada v8.
2. Pada  iterasi  berikutnya  untuk  K=  6  yang  berada pada kolom D(8) diperoleh penurunan jarak dari ∞  menjadi  15  itu  berarti  jalur  terpendek didapatkan adalah v6 maka dapat ditetapkan jalur terpendek adalah v6-v8
3. Pada  perhitungan  iterasi    yang  berikutnya  untuk K= 4 maka didapatkan penurun jalur pada kolom D(4)  diperoleh  penurunan  jarak  dari  15  ke  13 maka dapat ditetapkan jalur terpendek yang akan dilalui adalah sebagai berikut v4-v6-v8
4. Pada kolom D(4)  terjadi penuruna jarak dari 13 menjadi  11  pada  K=2  maka  didapatkan  jalur terpendek yaitu v2- -v4-v6-V8
5. Pada kolom D(2) terjadi penurunan jarak dari 11 menjadi  3  maka  ditatap  jalur  terpendek  nya adalah v1-v2-v4-v6-v8
Jadi jalur terpendek adalah v1- v2- v4 - v6 – v8 (P.Denai,  Jl.SM.Raja,  Pancing,  Yosusdarso,  Cemara, Krakatau.)dengan total panjang adalah 15.
UML  adalah  sebuah  bahasa  yang  berdasarkan grafik atau gambar untuk memvisualisasi,
menspesifikasikan, membangun, dan
pendokumentasian  dari  sebuah  sistem  pengembangan software berbasis  OO  ( Object-Oriented ). Unified Modeling  Language (UML),  himpunan  struktur  dan teknik  untuk  pemodelan  desain  program  berorientasi objek  (PBO)  serta  aplikasinya.  Perancangan  aplikasi
ini  menggunakan  dua  diagram  UML  antara  lain use case dan activity diagram. Use Case diagram adalah penjelasan- penjelasan  tentang  kegiatan  yang  user  lakukan  ketika menjalankan  sebuah  sistem.  Berikut  ini  adalah use case Diagram pada penentuan jalur terpendek.
Gambar 2 : Use Case Diagram

## IV. IMPLEMENTASI
1. Form home.
Form home merupakan halaman utama yang merupakan form induk dari aplikasi penentuan jalur terpendek yang dirancang yang berisi dari bebrapa menu yaitu pada gambar 3.
Gambar 3 : Form Home
2. Form Pengiriman Barang Form pengiriman barang merupakan bagian
pengingputan data-data barang dan jalur yang akan di lalui yang ada pada gambar 4.
Gambar  4 : Form Pengiriman Barang
Keterangan gambar form diatas adalah sebagai berikut: 1. No.Faktur berfungsi untuk pengingputan No.Faktur.
2. ID.Supir berfungsi untuk mengingput ID.Supir.
3. Jalur  berfungsi  untuk  mengingput  jalur-jalur  yang akan dilalui.
4. Tujuan  digunakan  untuk  mengingput  tujuan  yang akn dilalui.
5. Nama  penerima  merupakan  identitas  penerima barang.
3. Form Info
Form info merupakan menu pilihan pada menu info  terdapat dua menu pilihan yaitu menu info rute dan menu laporan pengirimaan yang dapat dilihat pada gambar 5 Gambar 5 : Form Info
4. Form Laporan Pengiriman
Form laporan pengiriman barang digunakan untuk melihat data terkirim atau tidaknya barang yang dikirimkan.
Gambar 6 : Form Laporan Pengiriman Barang
5. Form Info Rute
Form rute yang berisi rute jalan hasil pengujian pencarian jalur terpendek yang akan dilalui.
Gambar 7 : Form Info Rute
6. Form About Form about yang berisi tentang data diri penulis, yang dapat dilihat pada gambar 8 Gambar 8 : Form About

## V. KESIMPULAN
Berdasarkan analisa beberapa hal yang dapat ditarik kesimpul setelah menulis skripsi ini adalah sebagai berikut:
1. Pencarian  jalur  terpendek  dapat  menggunakan metode pencaian graf  sehingga   menemukan  jarak yang lebih efesien.
2. Penerapan  algoritma  Djikstra  pada  aplikasi pencarian rute terpendek  menghasilkan  jarak  yang lebih  dekat,  dengan  ini  penggunaan  algoritma Djikstra  dapat  membantu  pengiriman  barang PT.Kencana Link Nusantara Medan.
3. Aplikasi  penentuan  jalur  terpendek  telah  selesai dirancang,  dan  dapat  dijadikan  sebagai  aplikasi penentuan  jalur  terpendek  pada  PT.Kencana  Link Nusantara Medan.

## VI. DAFTAR PUSTAKA
[1]. Gata.Windu  &  Grace  Gata.  (2013). Sukses  Membangun Aplikasi  Penjualan    Dengan  Java .  Jakarta.  PT.Elex  Media Komputindo.
[2]. Munir.  Rinaldi.(2010). Matematika  Diskrit .  Bandung. Penerbit Informatika [3]. Munir.  Rinldi.  (2007). Algoritma  Dan  Pemerograman Dalam Bahasa Pascal Dan C . Bandung.Penerbit Informatika [4]. Peluang Bisnis Pengiriman Barang. (Manis Rukmini, 2011)
[5]. Sutabri.  Tata.(2012). Analisis  Sistem  Informasi .  Jakarta. Penerbit Andi.
[6]. Suarga  (2012) Algoritma  Dan  Pemerograman .  Yogyakarta. Penerbit Andi [7]. Siang.  Jong.  Jek  (2009) Matematika  Diskrit  Dan Aplikasinya  Pada  Ilmu  Komputer Yogyakarta.  Penerbit Andi [8]. Nugroho.  Adi.  (2009).    Rekayasa Perangkat  Lunak Berorentasi Objek . Yogyakarta. Penerbit Andi. [9]. Winarno. Edi. Ali. Zaki. SmitDev Community (2012). Visual Basic.NET. Jakarta. PT. Elex Media Komputindo