## EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi
Journal Homepage: http://ejurnal.ung.ac.id/index.php/Euler DOI: https://doi.org/10.34312/euler.v11i1.18244 Juni 2023, Vol. 11, No. 1, Hal. 55-65

## Algoritma Dijkstra dan Algoritma Greedy Untuk Optimasi Rute Pengiriman Barang Pada Kantor Pos Gorontalo
Novria Fatmawati Lakutu 1 , Muhammad Rifai Katili 2 , Sri Lestari Mahmud 3* , Nisky Imansyah Yahya 4
1,3,4 Jurusan Matematika, Universitas Negeri Gorontalo, Bone Bolango 96554, Indonesia
2 Jurusan Teknik Informatika, Universitas Negeri Gorontalo, Bone Bolango 96554, Indonesia
*Penulis Korespondensi. Email: sri.lestari@ung.ac.id

## Abstrak
Pengiriman barang merupakan salah satu jasa yang digunakan dalam proses jual beli online pada perusahaan Kantor Pos. Perusahaan perlu adanya suatu kinerja dalam pendistribusian barang lebih efisien waktu dan biaya sehingga memerlukan ketetapan dalam pemilihan jalur terpendek. Telah banyak  algoritma  yang  digunakan  untuk  membantu  menemukan  jalur  terpendek  pendistribusian barang di antaranya yaitu Algoritma Dijkstra dan Algoritma Greedy. Pada penelitian ini penerapan kedua  algoritma  tersebut  untuk  mencari  rute  antar  kelurahan  yang  menjadi  tujuan  pengiriman baranng,  kemudian  dibandingkan  untuk  melihat  algoritma  manakah  yang  lebih  optimal. Berdasarkan  hasil  perhitungan,  Algoritma  Dijkstra  dapat  memberikan  solusi  yang  lebih  optimal dengan total jarak tempuh yang diperoleh 304,90 Km sedangkan Algoritma Greedy menghasilkan total jarak tempuh 441,60 Km.
Kata Kunci: Rute Terpendek; Algoritma Dijkstra; Algoritma Greedy

## Abstract
Delivery of goods is one of the services used in the online buying and selling process at the Post Office  company.  Companies  need  a  performance  in  the  distribution  of  goods  that  is  more  time- consuming  and  cost-efficient,  so  it  requires  determination  in  selecting  the  shortest  path.  Many algorithms  have  been  used  to  help  find  the  shortest  path  for  distributing  goods,  including  the Dijkstra Algorithm and the Greedy Algorithm. In this study, the application of the two algorithms is to find routes between sub-districts that are the destination of goods delivery, then compare to see which algorithm is more optimal. Based on the calculation results, the Dijkstra Algorithm can provide  a  more  optimal  solution  with  a  total  mileage  obtained  of  304.90  Km,  while  the  Greedy Algorithm produces a total distance of 441.60 Km.
Keywords: Shortest Route; Dijkstra Algorithm; Greedy Algorithm

## 1. Pendahuluan
Matematika merupakan ilmu yang dapat memudahkan penyajian dan pemahaman pada suatu masalah [1]. Salah satu bidang matematika yang dapat menggambarkan representasi masalah adalah Teori Graf. Graf adalah grafik yang memuat informasi tertentu yang dengan cepat di interpretasikan untuk menjelaskan berbagai struktur yang ada, agar objek lebih mudah dipahami [2]. Graf juga dapat menyelesaikan  berbagai  masalah,  salah  satunya  adalah  masalah  optimasi.  Masalah  optimasi  yang dapat dipecahkan yaitu pencarian jalur terpendek. Jalur terpendek adalah pencarian lintasan terpendek antar simpul graf dan menghasilkan bobot terkecil [3]. Pencarian jalur terpendek ini telah digunakan di berbagai bidang untuk meminimalkan biaya atau mempersingkat proses [4].  Dalam teori graf, ada beberapa algoritma yang dapat digunakan untuk menyelesaikan masalah rute terpendek, antara lain algoritma Dijkstra, algoritma Bellmand Ford, algoritma Greedy, dan algoritma Floyd Warshall.
Algoritma  Dijkstra  merupakan  salah  satu  algoritma  yang  paling  mudah  untuk  di implementasikan  karena  algoritma  ini  merupakan  bagian  dari  program  dinamis  yang  menemukan
semua jalur terpendek antara setiap kemungkinan pasangan lokasi yang berbeda dan sangat efektif dalam  menyelesaikan  masalah  jalur  optimal  untuk  semua  pasangan  simpul.  Algoritma  ini memecahkan masalah pencarian rute terpendek (rute dengan panjang minimum) pada graf berbobot, bobotnya  adalah  bilangan  positif  sehingga  simpul  negatif  tidak  dapat  melewatinya,  tetapi  jika  ya, maka solusi yang diberikan adalah infinity [5]. Sedangkan Algoritma Greedy adalah algoritma yang memperoleh  solusi  optimal  dari  masalah  optimasi  dengan  cara  menyelesaikan-nya  langkah  demi langkah  [6].  Algoritma  Greedy  merupakan  algoritma  yang  dapat  memecahkan  masalah  dengan menemukan alternatif paling baik pada saat tertentu . Walaupun setiap solusi jawaban dari algoritma greedy  tidak  dipastikan  merupakan  solusi  optimum  global,  tetapi    dapat  diandalkan  untuk mengoptimasi waktu [7].
Permasalahan  yang  dapat  diterapkan  pada  pencarian  jalur  terpendek  yaitu  pada  pengiriman barang. Pengiriman barang merupakan salah satu jasa yang telah banyak digunakan masa kini. Hal tersebut dikarenakan jasa pengiriman barang berperan penting dalam segala kebutuhan, salah satunya dalam proses jual beli online. Di Indonesia, terdapat beberapa perusahaan yang bergerak pada bidang pengiriman, salah satunya yaitu PT. Pos Indonesiaa atau Kantor Pos, yang merupakan perusahaan besar  bergerak  di  bidang  pengiriman  barang.  Perusahaan  ini  pertama  kali  didirikan  di  Batavia (Jakarta) oleh gubernur Jendral G.W Baron Van Imhoff pada tanggal 26 Agustus 1746 [8]. Proses pengiriman  barang  yang  dilakukan  memiliki  beberapa  tahapan  yang  diawali  dengan  proses pencocokan  untuk  mengetahui  barang  dalam  keadaan  utuh  dan  tidak  rusak  kemudian  dilakukan proses penyerahan barang ke kurir dan selanjutnya melakukan pengiriman barang ke alamat-alamat yang  dituju.  Adapun  permasalahan  yang terjadi  diantaranya  keterlamabatan  pengiriman  barang  ke alamat tujuan karena banyaknya barang yang harus dikirim ke beberapa tempat yang berbeda. Hal ini karena  kantor  pos  masih  menggunakan  panduan  manual  (perkiraan)  untuk  menentukan  rute pengiriman. Untuk mengatasi masalah tersebut cara yang dapat di ambil oleh perusahaan menentukan rute distribusi yang optimal dengan mempertimbangkan jarak tempuh. Oleh karena itu, Kantor pos memerlukan  sebuah  kebijakan  pemilihan  rute  pengiriman  barang.  Hasil  dari  menentukan  rute terpendek dapat menjadi bahan peninjauan dalam pengambilan keputusan untuk menunjukan lintasan yang akan ditempuh.
Beberapa  penelitian  terkait  masalah  optimasi  telah  banyak  dilakukan  diantaranya  adalah Usman , et al. [9] meneliti tentang optimasi rute distribusi dalam menyalurkan produk obat dan barang dengan  menerapkan  Algoritma  Greedy  tujuannya  untuk  meminimalkan  biaya  pengiriman  dan meminimalkan  total  waktu  perjalanan  distribusi.  Hasil  perhitungan  menunjukan  rute  dalam melakukan  distribusi  pada  PT.  Z  lebih  optimal  dibandingkan  dengan  rute  sebelum  menggunakan Algoritma Greedy.  Cantona , et al . [10] membahas tentang optimasi dalam mencari rute terpendek yang diterapkan pada smartphone, pengguna dapat menghemat waktu mencari museum di Jakarta. Hasil  penelitian  yang  diperoleh  bahwa  Algoritma  Dijkstra  mendapatkan  rute  terpendek  dengan memerlukan 7 bobot yang mana hanya perlu 35% untuk mencapai museum di Jakarta.
Pada penelitian sebelumnya yang dilakukan  [11] meneliti tentang optimasi jalur bus kampus menuju Kampus UNG Bone Bolango dengan menerapkan Algoritma Dijkstra. Hasil di dapat bahwa algoritma Dijkstra menghasilkan solusi yang optimal dengan lintasan terpendek dari V1 ke V16 atau dengan keterangan (Kampus 1 UNG ke Kampus 4 UNG Bone Bolango) dengan bobot jarak tempuh 99,5 Km. Di samping penelitian yang dilakukan Arviantino , et al . [12] penelitian tersebut membahas tentang penerapan Algoritma Greedy dalam mencari titik nilai terkecil dengan menghitung jalur yang dilewati. Hasil dari penelitian tersebut menunjukkan bahwa rute yang dikunjungi untuk safari dakwah pada semua masjid dimulai dari titik ADCEFGB dengan durasi waktu yang optimal. Berbeda dari penelitian-penelitian  sebelumnya,  pada  penelitian  ini  dilakukan  optimasi  pencarian  rute  terpendek pada  Kantor  Pos  Gorontalo  dengan  menerapkan  Algoritma  Dijkstra  dan  Algoritma  Greedy  untuk mengoptimalkan  rute  pengiriman  barang  dengan  menghitung  jarak  terpendek  di  masing-masing alamat yang dituju.

## 2.  Metode Penelitian
Penelitian ini merupakan penelitiaan kuantitatif dengan studi kasus distribusi barang di Kantor Pos Gorontalo. Data yang digunakan dalam penelitian ini adalah data primer yang diperoleh hasil melakukan  wawancara  dan  observasi  kepada  pihak  penanggung  jawab  di  Kantor  Pos  Gorontalo, dengan langkah-langkah sebagai berikut:
1) Studi pendahuluan dimana pada Penelitian ini menelaah jurnal, artikel dan referensi yang akan digunakan dalam penelitian.
2) Merumuskan masalah dengan melakukan wawancara dan observasi.
3) Mengumpulkan data yang dibutuhkan berupa data lokasi.
4) Mengolah data dengan menerapkan Algoritma Dijkstra dan Algoritma Greedy
5) Menginterpretasikan  data  dengan  menggunakan  kedua  Algoritma  untuk  mendapatkan  solusi rute terpendek kemudian dibuat kesimpulan dari hasil penelitian yang dilakukan.
Tahapan-tahapan  yang  di  gunakan  dalam  menerapkan  Algoritma  Dijkstra  dan  Algoritma Greedy dapat dilihat pada Gambar 1.

## Gambar 1. Diagram Alir Penelitian

## 3. Hasil dan Pembahasan
PT. Pos Indonesia (Persero) merupakan salah satu Badan Usaha Milik Negara (BUMN) yang bergerak  dalam  bidang  jasa  pengiriman  surat  maupun  barang.  Cabang  PT.  Pos  Indonesia  salah satunya terletak di Kota Gorontalo. Berdasarkan hasil observasi yang dilakukan, penyaluran barang di Kantor Pos ini terbagi menjadi beberapa wilayah. Pada penelitian ini di batasi ke 9 Kecamatan yang ada di Kota Gorontalo untuk digunakan sebagai penentuan rute terpendek dari setiap kelurahan yang  ada  di  suatu  Kecamatan  dengan  menerapkan  dua  algoritma  yaitu  Algoritma  Dijkstra  dan Algoritma Greedy. Dalam proses penyaluran barang pada Kantor Pos Gorontalo sebagai simpul awal
meuju ke lokasi penyaluran atau sebagai simpul tujuan dengan total  50 simpul yang disajikan pada Tabel 1.
Tabel 1. Keterangan Simpul pada Graf Simpul Keterangan Simpul Keterangan 𝑉 0 Kantor Pos Gorontalo 𝑉 26 Kelurahan Dembe 1 𝑉 1 Kelurahan Ipilo 𝑉 27 Kelurahan Pilolodaa 𝑉 2 Kelurahan Biawao 𝑉 28 Kelurahan Tuladenggi 𝑉 3 Kelurahan Tenda 𝑉 29 Kelurahan Buladu 𝑉 4 Kelurahan Bugis 𝑉 30 Kelurahan Molosipat W 𝑉 5 Kelurahan Biawu 𝑉 31 Kelurahan Libuo 𝑉 6 Kelurahan Limba B 𝑉 32 Kelurahan Huangobotu 𝑉 7 Kelurahan Heledulaa Selatan 𝑉 33 Kelurahan Wumialo 𝑉 8 Kelurahan Limba U1 𝑉 34 Kelurahan Dulalowo 𝑉 9 Kelurahan Limba U2 𝑉 35 Kelurahan Dulalowo Timur 𝑉 10 Kelurahan Heledulaa 𝑉 36 Kelurahan Liluwo 𝑉 11 Kelurahan Moodu 𝑉 37 Kelurahan Pulubala 𝑉 12 Kelurahan Dembe 2 𝑉 38 Kelurahan Paguyaman 𝑉 13 Kelurahan Tamalate 𝑉 39 Kelurahan Tomulabutao 𝑉 14 Kelurahan Padebuolo 𝑉 40 Kelurahan Tomulabutao Selatan 𝑉 15 Kelurahan Botu 𝑉 41 Kelurahan Tapa 𝑉 16 Kelurahan Talumolo 𝑉 42 Kelurahan Molosipat U 𝑉 17 Kelurahan Leato Utara 𝑉 43 Kelurahan Tanggikiki 𝑉 18 Kelurahan Leato Selatan 𝑉 44 Kelurahan Bulotadaa 𝑉 19 Kelurahan Tanjung Kramat 𝑉 45 Kelurahan Bulotadaa Timur 𝑉 20 Kelurahan Pohe 𝑉 46 Kelurahan Dulomo 𝑉 21 Kelurahan Siendeng 𝑉 47 Kelurahan Dulomo Selatan 𝑉 22 Kelurahan Donggala 𝑉 48 Kelurahan Wongkaditi Barat 𝑉 23 Kelurahan Tenilo 𝑉 49 Kelurahan Wongkaditi Timur 𝑉 24 Kelurahan Buliide 𝑉 50 Kelurahan Dembe Jaya 𝑉 25 Kelurahan Lekobalo
Tabel  1.  merupakan  keterangan  dari  letak  50  simpul  pada  graf  berbobot  yang  di interpretasikan dalam bentuk Graf yang disajikan pada Gambar 1.

## 3.1 Menentukan Rute Terpendek Menggunakan Algoritma Dijkstra
Algoritma Dijkstra adalah sebuah variasi dari algoritma populer untuk memecahkan masalah optimisasi dan bersifat sederhana [13]. Langkah Algoritma Dijkstra menggunakan pendekatan dalam dalam penentuan lintasan terpendek dari suatu titik tertentu ke setiap titik lain pada suatu graf dengan pengulangan  sebanyak |𝑉(𝐺)| − 1 ,  sehingga  membentuk  pohon  pembangun  Dijkstra  setelah pengulangan terakhir dari Graf [14]. Berikut perubahan bobot dari setiap iterasi yang disajikan pada Tabel 2.
Tabel 2 . Daftar Bobot Antar Jarak No Sisi Bobot   No Sisi Bobot  No Sisi Bobot 1 𝑉 0 − 𝑉 1 0,95 27 𝑉 13 − 𝑉 12 2,0 53 𝑉 35 − 𝑉 36 1,6 2 𝑉 0 − 𝑉 2 0,90 28 𝑉 14 − 𝑉 15 2,0 54 𝑉 35 − 𝑉 33 1,6 3 𝑉 0 − 𝑉 3 1,5 29 𝑉 14 − 𝑉 11 1,6 55 𝑉 36 − 𝑉 38 1,3 4 𝑉 0 − 𝑉 4 0,65 30 𝑉 15 − 𝑉 13 7,3 56 𝑉 37 − 𝑉 41 1,0 5 𝑉 1 − 𝑉 4 0,60 31 𝑉 15 − 𝑉 18 6,5 57 𝑉 37 − 𝑉 40 1,4 6 𝑉 1 − 𝑉 7 0,80 32 𝑉 16 − 𝑉 17 4,3 58 𝑉 38 − 𝑉 41 0,75
7 𝑉 1 − 𝑉 14 1,4 33 𝑉 17 − 𝑉 18 1,9 59 𝑉 38 − 𝑉 35 2,1 8 𝑉 2 − 𝑉 7 0,95 34 𝑉 20 − 𝑉 19 5,4 60 𝑉 38 − 𝑉 44 2,1 9 𝑉 2 − 𝑉 8 1,1 35 𝑉 21 − 𝑉 19 1,7 61 𝑉 39 − 𝑉 40 0,80 10 𝑉 2 − 𝑉 5 0,50 36 𝑉 21 − 𝑉 22 3,3 62 𝑉 40 − 𝑉 32 1,0
11 𝑉 3 − 𝑉 20 3,4 37 𝑉 22 − 𝑉 23 2,6 63 𝑉 41 − 𝑉 39 2,1 12 𝑉 4 − 𝑉 16 1,5 38 𝑉 23 − 𝑉 24 4,1 64 𝑉 41 − 𝑉 42 0,95 13 𝑉 5 − 𝑉 21 1,8 39 𝑉 24 − 𝑉 27 3,1 65 𝑉 43 − 𝑉 45 1,2 14 𝑉 5 − 𝑉 30 2,4 40 𝑉 24 − 𝑉 25 1,3 66 𝑉 43 − 𝑉 38 1,3 15 𝑉 5 − 𝑉 22 1,7 41 𝑉 25 − 𝑉 27 5,3 67 𝑉 44 − 𝑉 42 1,1
16 𝑉 6 − 𝑉 5 0,95 42 𝑉 25 − 𝑉 26 1,5 68 𝑉 45 − 𝑉 44 1,6 17 𝑉 7 − 𝑉 10 1,2 43 𝑉 28 − 𝑉 29 5,0 69 𝑉 46 − 𝑉 45 2,0 18 𝑉 8 − 𝑉 6 1,3 44 𝑉 29 − 𝑉 26 2,2 70 𝑉 47 − 𝑉 46 1,0 19 𝑉 8 − 𝑉 9 1,0 45 𝑉 29 − 𝑉 24 1,5 71 𝑉 48 − 𝑉 36 2,8 20 𝑉 9 − 𝑉 35 1,4 46 𝑉 29 − 𝑉 31 2,6 72 𝑉 48 − 𝑉 46 2,5 21 𝑉 9 − 𝑉 33 1,2 47 𝑉 30 − 𝑉 29 1,6 73 𝑉 48 − 𝑉 43 2,3 22 𝑉 10 − 𝑉 11 2,4 48 𝑉 31 − 𝑉 32 2,2 74 𝑉 49 − 𝑉 47 2,5 23 𝑉 11 − 𝑉 12 1,2 49 𝑉 32 − 𝑉 28 1,4 75 𝑉 49 − 𝑉 50 1,2 24 𝑉 12 − 𝑉 50 2,2 50 𝑉 33 − 𝑉 31 1,0 76 𝑉 50 − 𝑉 48 1,0 25 𝑉 12 − 𝑉 49 1,5 51 𝑉 33 − 𝑉 34 1,1 77 𝑉 50 − 𝑉 47 2,1 26 𝑉 13 − 𝑉 11 1,8 52 𝑉 34 − 𝑉 37
Selanjutnya, penyelesaian perhitungan iterasi yang dapat dilihat pada Tabel 2.
Tabel 2. Perhitungan Iterasi Berdasarkan Algoritma Dijkstra Vertex  Bobot  Vertex  Bobot  Vertex  Bobot  Vertex  Bobot  Vertex  Bobot
1 0 11 ∞ 21 ∞ 31 ∞ 41 ∞ 2 0,95 12 ∞ 22 ∞ 32 ∞ 42 ∞ 3 0,9 13 ∞ 23 ∞ 33 ∞ 43 ∞ 4 1,5 14 ∞ 24 ∞ 34 ∞ 44 ∞ 5 0,65 15 ∞ 25 ∞ 45 ∞ 45 ∞ 6 ∞ 16 2,15 26 ∞ 36 ∞ 46 ∞ 7 ∞ 17 ∞ 27 ∞ 37 ∞ 47 ∞ 8 ∞ 18 ∞ 28 ∞ 38 ∞ 48 ∞ 9 ∞ 19 ∞ 29 ∞ 39 ∞ 49 ∞ 10 ∞ 20 ∞ 30 ∞ 40 ∞ 50 ∞
Iterasi 1 pada Tabel 2. dapat dijelaskan bahwa simpul 𝑉 0 terhubung dengan simpul 𝑉 1 , 𝑉 2 , 𝑉 3 dan 𝑉 4 dengan  bobot 𝑉 0 − 𝑉 1 = 0,95, 𝑉 0 − 𝑉 2 = 0,90, 𝑉 0 − 𝑉 3 = 1,5 dan 𝑉 0 − 𝑉 4 = 0,65 .  Karena simpul 𝑉 4 bobot terkecil dari semua titik yang berhubungan dengan 𝑉 0 maka simpul 𝑉 4 memiliki label tetap  atau  permanen  yang  artinya  simpul  tersebut  memiliki  nilai  yang  lebih  kecil.  Selanjutnya turunkan simpul 𝑉 4 . Sehigga diperoleh iterasi selanjutnya yang dapat dilihat pada Tabel 3.
Tabel 3. Lanjutan Perhitungan Iterasi berdasarkan Algoritma Dijkstra Vertex  Bobot  Vertex  Bobot  Vertex  Bobot  Vertex  Bobot  Vertex  Bobot
1 0 11 ∞ 21 ∞ 31 ∞ 41 ∞ 2 0,95 12 ∞ 22 ∞ 32 ∞ 42 ∞ 3 0,9 13 ∞ 23 ∞ 33 ∞ 43 ∞ 4 1,5 14 ∞ 24 ∞ 34 ∞ 44 ∞ 5 0,65 15 ∞ 25 ∞ 45 ∞ 45 ∞ 6 ∞ 16 2,15 26 ∞ 36 ∞ 46 ∞ 7 17 ∞ 27 ∞ 37 ∞ 47 ∞ 8 ∞ 18 ∞ 28 ∞ 38 ∞ 48 ∞ 9 ∞ 19 ∞ 29 ∞ 39 ∞ 49 ∞ 10 ∞ 20 ∞ 30 ∞ 40 ∞ 50 ∞
Iterasi 2 pada Tabel 3. dapat dijelaskan bahwa simpul 𝑉 4 terhubung dengan simpul 𝑉 16 dengan bobot 𝑉 4 − 𝑉 16 = 1,5 kemudian tambahkan dengan bobot yang sudah diwarnai (0,65 + 1,5 = 2,15) . Karena  simpul 𝑉 2 bobot  terkecil  maka  maka  simpul 𝑉 2 memiliki  label  tetap  atau  permanen  yang artinya  simpul  tersebut  memiliki  nilai  yang  lebih  kecil,  selanjutnya  turunkan  simpul 𝑉 2 .  Sehigga diperoleh iterasi selanjutnya.
Dengan  melakukan  langkah  yang  sama  pada  setiap  iterasi  sampai  mencapai  batas maksimal iterasi 𝐾 = 50 maka diperoleh hasil  perhitungan rute terpendek menggunakan Algoritma  Dijkstra yaitu 𝑉 0 − 𝑉 4 − 𝑉 16 − 𝑉 17 − 𝑉 18 − 𝑉 15 − 𝑉 13 − 𝑉 14 − 𝑉 11 − 𝑉 12 − 𝑉 49 − 𝑉 50 − 𝑉 48 − 𝑉 47 − 𝑉 46 − 𝑉 43 − 𝑉 38 − 𝑉 36 − 𝑉 35 − 𝑉 45 − 𝑉 44 − 𝑉 41 − 𝑉 39 − 𝑉 40 − 𝑉 37 − 𝑉 34 − 𝑉 33 − 𝑉 31 − 𝑉 32 − 𝑉 28 − 𝑉 26 − 𝑉 25 − 𝑉 27 − 𝑉 24 − 𝑉 29 − 𝑉 23 − 𝑉 22 − 𝑉 21 − 𝑉 19 − 𝑉 20 − 𝑉 3 − 𝑉 5 − 𝑉 30 − 𝑉 6 − 𝑉 8 − 𝑉 9 − 𝑉 2 − 𝑉 7 − 𝑉 10 − 𝑉 1 , dengan total jarak keseluruhan 304,9 Km.

## 3.2 Menentukan Rute Terpendek Menggunakan Algoritma Greedy
Selanjutnya  akan  dilakukan  pencarian  lintasan  terpendek  dari  graf  berbobot  yang  telah terbentuk  dengan  menerapkan  Algoritma  Greedy.  Algoritma  greedy  yaitu  algoritma  yang memecahkan  masalah  langkah  demi  langkah  dan  merupakan  salah  satu  metode  untuk  masalah optimasi.  Beberapa  permasalahan  mungkin  tidak  memiliki  solusi  yang  efektif,  tetapi  algoritma Greedy dapat memberikan solusi yang hampir optimal dan efektif. Solusi yang dapat dibentuk dengan algoritma Greedy setiap langkah yaitu dalam setiap langkah, pilihan harus merupakan pilihan terbaik, pilihan  yang  dibuat  dalam  satu  langkah  tidak  dapat  diubah  pada  langkah  berikutnya,  kemudian Metode yang digunakan oleh algoritma greedy adalah dengan menentukan local optimum pada setiap langkah. Masalah optimasi algoritma greedy ditentukan oleh bagian-bagian berikut [14]. Komponen- komponen dari Algoritma Greedy adalah:
1) Himpunan  kandidat.  Set  berisi  komponen  yang  membuat  solusi.  Untuk  masalah  lintasan terpendek graf, himpunan kandidat ini adalah himpunan simpul dari graf.
2) Himpunan solusi. Set solusi berisi kandidat yang dipilih sebagai solusi untuk masalah tersebut. Himpunan ini merupakan bagian dari himpunan kandidat atau kandidat tetapi tidak semua atau dengan kata lain himpunan penyelesaian ini merupakan bagian dari himpunan kandidat.
3) Fungsi seleksi. Fungsi seleksi diwakili oleh predikat seleksi. Pemilihan predikat adalah fungsi yang  ada  pada  setiap  langkah,  memilih  kandidat  yang  paling  mungkin  memenuhi  solusi
optimal.  Kandidat  yang terpilih  pada  satu  tahap  tidak akan  dipertimbangkan lagi  pada tahap selanjutnya.
4) Fungsi kelayakan. Fitur yang menunjukkan apakah kandidat terpilih dapat memberikan solusi yang layak.
5) Fungsi  tujuan.  Tindakan  yang  memaksimalkan  dan  meminimalkan  nilai  solusi.  Tujuannya adalah untuk memilih solusi terbaik dari setiap komponen himpunan solusi.
Perhitungan akan dilakukan dari simpul awal yaitu Kantor Pos Gorontalo menuju ke alamat untuk penyaluran barang dari setiap simpul sebagai berikut [15]:
1) Periksa  semua  sisi  yang  berbatasan  langsung  dengan  simpul;  a)  Pilih  tepi  dengan  bobot terendah. Tepi ini pertama-tama menjadi jalur terpendek, sebut saja 𝐿(1) .
2) Hitungg jalur terpendek kedua sebagai berikut:
3) Menghitung: 𝑑(𝑖) = panjang 𝐿(1) + bobot sisi dari simpul terakhir 𝐿(1) ke simpul kedua 𝑖 . 4) Pilih 𝑑(𝑖) terkecil. Bandingkan 𝑑(𝑖) dengan bobot sisi (𝑎;  𝑖) . Jika bobot sisi (𝑎; 𝑖) lebih kecil dari 𝑑(𝑖) , maka 𝐿(2)   =  𝐿(1) 𝑈 (tepi dari simpul terakhir di 𝐿(𝑖) adalah simpul (𝑖) .
5) Demikian pula, ulangi langkah 2 untuk menentukan rute terpendek berikutnya.
Berdasarkan  langkah-langkah  pada  Algoritma  Greedy  maka  diperoleh  proses  iterasi  sebagai berikut:
1) Proses perhitungan Iterasi 1
Himpunan Kandidat: Kantor Pos Gorontalo ke Kelurahan Ipilo. Himpunan Solusi: simpul 𝑉 0 − 𝑉 1 Fungsi Seleksi : 𝑉 0 − 𝑉 1 Fungsi Kelayakan: 𝑉 0 − 𝑉 1 Fungsi Objektif: 𝑉 0 − 𝑉 1 .
Karena simpul 𝑉 0 terhubung dengan simpul 𝑉 1 untuk menuju ke simpul 𝑉 1 dengan bobot lebih optimal maka hasil yang diperoleh untuk menentukan jalur terpendek menggunakan algoritma greedy simpul 𝑉 0 − 𝑉 1 , dengan jarak 0,95 Km. Yang disajikan pada Gambar 2.
Gambar 2. Perhitungan Iterasi berdasarkan Algoritma Greedy
2) Proses perhitungan Iterasi 2
Himpunan Kandidat: Kantor Pos Gorontalo ke Kelurahan Biawao. Himpunan Solusi: simpul 𝑉 0 − 𝑉 2 Fungsi Seleksi : 𝑉 0 − 𝑉 2 Fungsi Kelayakan: 𝑉 0 − 𝑉 2 Fungsi Objektif: 𝑉 0 − 𝑉 2 .
Karena simpul 𝑉 0 terhubung dengan simpul 𝑉 2 untuk menuju ke simpul 𝑉 2 dengan bobot lebih optimal  maka  hasil  yang  diperoleh  menentukan  jalur  terpendek  menggunakan  algoritma  greedy melalui simpul 𝑉 0 − 𝑉 2 , dengan jarak 0,90 Km. Yang disajikan pada Gambar 3.
Gambar 3. Lanjutan perhitungan Iterasi berdasarkan Algoritma Greedy
Dengan  melakukan  langkah  yang  sama  untuk  melakukan  perhitungan  antar  kelurahan  maka hasil perhitungan di dapatkan sampai iterasi ke 50 dengan total jarak keseluruhan 441,6 Km.

## 3.3 Perbandingan Algoritma Dijkstra dan Algoritma Greedy
Untuk melihat perbandingan rute pada kelurahan yang di tampilkan dengan menerapkan kedua algoritma disajikan pada Tabel 4.
Tabel 4. Perbandingaan Rute Kelurahan Algoritma Dijkstra Algoritma Greedy Heledulaa Selatan 𝑉 0 − 𝑉 1 − 𝑉 7 𝑉 0 − 𝑉 2 − 𝑉 7
Libuo 𝑉 0 − 𝑉 2 − 𝑉 8 − 𝑉 9 − 𝑉 33 − 𝑉 31 𝑉 0 − 𝑉 2 − 𝑉 5 − 𝑉 30 − 𝑉 29 − 𝑉 31
Bulotadaa 𝑉 0 − 𝑉 2 − 𝑉 8 − 𝑉 9 − 𝑉 35 − 𝑉 36 − 𝑉 38 − 𝑉 44 𝑉 0 − 𝑉 2 − 𝑉 7 − 𝑉 10 − 𝑉 11 − 𝑉 12 − 𝑉 49 − 𝑉 50 − 𝑉 48 − 𝑉 43 − 𝑉 45 − 𝑉 44
Pilolodaa 𝑉 0 − 𝑉 2 − 𝑉 5 − 𝑉 30 − 𝑉 29 − 𝑉 24 − 𝑉 27 𝑉 0 − 𝑉 2 − 𝑉 5 − 𝑉 22 − 𝑉 23 − 𝑉 24 − 𝑉 25 − 𝑉 27 Tomulabutao
Selatan
𝑉 0 − 𝑉 2 − 𝑉 8 − 𝑉 9 − 𝑉 33 − 𝑉 34 − 𝑉 37 − 𝑉 40 𝑉 0 − 𝑉 2 − 𝑉 7 − 𝑉 10 − 𝑉 11 − 𝑉 12 − 𝑉 49 − 𝑉 50 − 𝑉 48 − 𝑉 43 − 𝑉 38 − 𝑉 41 − 𝑉 39 − 𝑉 40
Selajutnya akan disajikan ke dalam bentuk Gambar Graf  berikut:

## 1. Rute Kelurahan Heledulaa Selatan

## 2. Rute Kelurahan Libuo
Gambar 6 . Rute dengan Algoritma Dijkstra Gambar 7. Rute dengan Algoritma Greedy 3. Rute Kelurahan Bulotadaa
Gambar 8 . Rute dengan Algoritma Dijkstra Gambar 9. Rute dengan Algoritma Greedy 4. Rute Kelurahan Pilolodaa
Gambar 10 . Rute dengan Algoritma Dijkstra Gambar 11. Rute dengan Algoritma Greedy 5. Rute Kelurahan Tomulabutao Selatan
Berdasarkan hasil perbandingan, rute optimal yang diperoleh dari perhitungan masing-masing algoritma memiliki hasil yang berbeda, dimana Algoritma Dijkstra memiliki jarak tempuh yang lebih kecil jika dibandigkan dengan jarak tempuh pada Algoritma Greedy. Dalam proses pencarian iterasi dari kedua algoritma, Algoritma Dijkstra bekerja secara menyeluruh terhadap alternatif fungsi yang ada, hingga rute terpendek tidak hanya dari simpul awal ke simpul tujuan, tetapi jalur terpendek dapat diperoleh  dari  semua  simpul.  Dimana  masing-masing  simpul  memiliki  bobot  jarak  yang  telah ditentukan. Hal ini karena algoritma Dijkstra melibatkan penempatan label ke setiap simpul. Misalkan 𝑳 𝒗 menyatakan label dari simpul 𝒗 . Dari setiap penjelasan, beberapa simpul memiliki label sementara dan  yang  lain  memiliki  label  tetap.  Dalam  mendeskripsikan  algoritma,  simpul  dengan pengidentifikasi  tetap  dilingkari.  Setiap  iterasi  dari  algoritma  tersebut  mengubah  status  label  dari semenntara  menjadi  tetap,  akibatnya  algoritma  dapat  berakhir  ketika  simpul  yang nilai  lebih  kecil menerima sebuah label tetap.  Sedangkan algoritma Greedy tidak sepenuhnya bekerja pada semua alternatif fungsi yang ada, sehingga diperoleh rute terpendek hanya dari simpul awal ke simpul tujuan. Algoritma Greedy kurang efisien saat digunakan untuk mencari rute terpendek dengan banyak simpul yang  bercabang  karena  Algoritma  Greedy  tergantung  pada  bobot  setiap  simpulnya,  sehingga  rute yang  dihasilkan  kurang  optimal.  Algoritma  greedy  hanya  dapat  di  implementasikan  pada  kasus pencarian rute terpendek yang memiliki jarak antar simpul tidak banyak atau pendek.  Oleh karena itu, algoritma Dijkstra merupakan algoritma yang optimal dalam menentukan rute pengiriman barang pada Kantor Pos Gorontalo dengan memperhatikan rute terpendek.

## 4. Kesimpulan
Berdasarkan hasil analisis dapat disimpulkan bahwa dalam menentukan rute optimal dengan menerapkan  Algoritma  Dijkstra  memiliki  total  jarak  tempuh  yaitu  304,90  Km.  Hasil  rute  dengan menerapan  Algoritma  Greedy  memiliki  total  jarak  tempuh  yaitu  441,60  Km.  Hal  ini  menunjukan bahwa  Algoritma  Dijkstra  merupakan  algoritma  yang  dapat  memberikan  hasil  optimal  dalam menentukan  rute  pengiriman  barang  pada  Kantor  Pos  Gorontalo  dengan  memperhatikan  jarak terpendek.

## Referensi
[1] L. Maro, and L. K. S. Purab, "Penerapan Konsep Pewarnaan Graf dalam Penyusunan Jadwal Perkuliahan  Menggunakan  Metode  AlgoritmaWelch-Powell  pada  Program  Studi  Teknik Informatika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Tribuana Kalabahi," Jurnal  Ilmiah  Wahana  Pendidikan  (JIWP) ,  vol.  7,  no.  6,  pp.  193–197,  2021.  doi: https://doi.org/10.5281/zenodo.5574383
[2] J. Siang, Matematika Diskrit dan Aplikasinya pada Ilmu Komputer . Yogyakarta: Andi, 2009.
[3]     N. Nurdianti, Penerapan Algoritma Greedy Untuk Menentukan Rute Terpendek Antar Klinik Gigi . Skripsi: Universitas Islam Negeri Sumatra Utara, 2020.
[4] M.  K.  Harahap,  and  N.  Khairina,  "Pencarian  Jalur  Terpendek  dengan  Algoritma  Dijkstra. SinkrOn , vol. 2, no. 2, p. 18, 2017. doi: https://doi.org/10.33395/sinkron.v2i2.61
[5]    I. K. Budayasa, Teori Graph dan Aplikasinya . Surabaya: Unesa University Press, 2007.
[6]   Y. D. Mahendra, N. Nuryanto, and A. Burhanuddin, "Sistem Penentuan Jarak Terdekat Dalam Pengiriman Darah Di Pmi Kota Semarang Dengan Metode Algoritma Greedy," Jurnal Komtika , vol. 2, no. 2, pp. 136–142, 2019. doi: https://doi.org/10.31603/komtika.v2i2.2601
[7] Y.  Darnita,  and  R.  Toyib,  "Penerapan  Algoritma  Greedy  Dalam  Pencarian  Jalur  Terpendek Pada Instansi-Instasi Penting Di Kota Argamakmur Kabupaten Bengkulu Utara," Jurnal Media Infotama , vol. 15, no. 2, pp. 57-64, 2019. doi:  https://doi.org/10.37676/jmi.v15i2.867
[8]  Pos Indonesia, http://www.posindonesia.co.id/index.php/profil-perusahaan/sejarah-pos, 2017.
[9]    M.  Z.  Usman,  and  T.  Oktiarso,  "Implementasi  Algoritma  Greedy  Untuk  Menyelesaikan Travelling Salesman Problem di Distributor PT. Z," Journal of Integrated System , vol. 1, no. 2, pp. 216–229, 2019. doi: https://doi.org/10.28932/jis.v1i2.1049
[10] A. Cantona, F. Fauziah, and W. Winarsih, "Implementasi Algoritma Dijkstra Pada Pencarian Rute Terpendek ke Museum di Jakarta," Jurnal Teknologi Dan Manajemen Informatika , vol. 6, no. 1, pp. 27–34, 2020. doi: https://doi.org/10.26905/jtmi.v6i1.3837
[11] N.  Nurwan,  W.  E.  Pranata,  M.  R.  F.  Payu,  and  N.  I.  Yahya,  "Implementation  of  Dijkstra Algorithm and Welch-Powell Algorithm for Optimal Solution of Campus Bus Transportation. Jurnal Matematika MANTIK , vol. 7, no. 1, pp. 31–40, 2021. doi: https://doi.org/10.15642/mantik.2021.7.1.31-40
[12]  F.  N.  Arviantino,  W.  Gata,  L.  Kurniawati,  Y.  A.  Setiawan,  and  D.  Priansyah,  "Penerapan Algoritma Greedy Dalam Pencarian Jalur Terpendek Pada Masjid–Masjid Di Kota Samarinda," Metik Jurnal , vol. 5 , no. 1, pp. 8–11, 2021. doi: https://doi.org/10.47002/metik.v5i1.188
[13]  J. S. Iskandar, and Y. F. Riti, "Perbandingan Algoritma Greedy dan Algoritma Dijkstra dalam Pencarian  Rute  Terpendek  dari  Kabupaten  Tuban  ke  Kota  Surabaya," PETIK:  Jurnal Pendidikan  Teknologi  Informasi  dan  Komunikasi, vol.  8,  no.  2,  pp.  96–106,  2022.  doi: https://doi.org/10.31980/jpetik.v8i2.1756
[14]  F.  Hartanto,  and  Y.  Safitri,  "Rancang  bangun  aplikasi  pencarian  lokasi  wisata  Kota  Bogor Menggunakan algoritma Greedy Berbasis Android," Jurnal Techno Nusa Mandiri , vol. 11, no. 2, pp. 169–175, 2014
[15]  S.  Oktaviana,  and  A.  Naufal,  "Algoritma  Greedy  untuk  Optimalisasi  Ruangan  dalam Penyusunan  Jadwal  Perkuliahan," Multinetics ,  vol.  3,  no.  1,  pp.  54-59,  2017.  doi: https://doi.org/10.32722/vol3.no1.2017.pp54-59