## Jurnal Pendidikan Teknologi Informasi
17 Issn :2460-7274 E-Issn:26858177 UMP

## BITNET

## JURNAL PENDIDIKAN TEKNOLOGI INFORMASI
http://journal.umpalangkaraya.ac.id/index.php/bitnet Volume 6 Nomor 2, September 2021 (17-24)
PERBANDINGAN ALGORITMA PRIM, KRUSKAL, DJIKSTRA, DAN FLOYD- WARSHALL UNTUK MEMECAHKAN MASALAH MINIMUM SPANNING TRESS:
PERANCANGAN PEMASANGAN PIPA SALURAN AIR BERSIH Comparison Of Prim, Kruskal, Djikstra, And Floyd-Warshall Algorithms To Solve Minimum Spanning Tree Problems: Design Of Clean Water Pipeline Installation
1 Ni Putu Diah Untari Ningsih dan 2 Muhammad Noor Fitriyanto
1 STKIP Agama Hindu Amlapura, Bali, Indonesia.
2 Universitas Muhammadiyah Palangkaraya, Kalimantan Tengah, Indonesia.

## ARTIKEL INFO
Diterima Agustus 2021 Dipublikasi September 2021
*e-mail : 1 niputudiahun@gmail.com 2 riyan.umpalangkaraya@gmail. com

## ABSTRAK
Kehidupan sehari-hari terdapat permasalahan mengenai optimasi yang dapat diselesaikan  menggunakan  pohon  rentang  minimum,  atau  dikenal  dengan  istilah Minimum  Spanning  Tree  (MST),  misalnya  masalah  mencari  biaya  termurah  dalam perancangan  pemasangan  pipa  saluran  air  bersih.  Ilmu  perancangan  pipa  termasuk dalam ilmu plumbing yang merupakan bagian dari ilmu teknik sipil. Peneliti tertarik untuk  menggunakan  algorima  Prim,  Kruskal,  Djikstra,  dan  Floyd-Warshall  untuk menyelesaikan  masalah  pohon  merentang  minimum  pada  pemasangan  pipa  saluran air dengan meneliti biaya minimumnya.
Hasil penelitian pohon rentang minimum dari jalur distribusi pipa saluran air bersih di Perumahan “X” dengan menggunakan algoritma Prim, Kruskal, dan Floyd -
Warshall  diperoleh  total  biaya  minimum  yang  sama  yaitu  sebesar  Rp.  5.600.000,-.
Sedangkan  algoritma  Djikstra  memperoleh  total  biaya  sebesar  Rp.  7.200.000,-.  Ini berarti  bila  ingin  mendapatkan  biaya  yang  paling  murah  dalam  merancang  instalasi pipa untuk air bersih, seorang estimator bisa menggunakan algoritma prim, kruskal, ataupun Floyd-Warshall.
Kata Kunci: Plumbing, Algoritma Prim, Kruskal, Djikstra, Floyd-Warshall

## ABSTRACT
Everyday life there are problems regarding optimization that can be solved using a minimum  span  tree,  or  known  as  the  Minimum  Spanning  Tree  (MST),  for  example  the problem  of  finding  the  lowest  cost  in  the  design  of  a  clean  water  pipe  installation.  The science  of  pipe  design  is  included  in  the  science  of  plumbing  which  is  part  of  civil engineering. Researchers are interested in using Prim, Kruskal, Djikstra, and Floyd-Warshall algorithms  to  solve  the  problem  of  minimum  spanning  trees  in  the  installation  of  water pipes by examining the minimum cost.
The results of the study of the minimum span trees of the distribution pipeline in the  "X"  Housing  using  Prim,  Kruskal,  and  Floyd-Warshall  algorithms  obtained  the  same minimum total cost of Rp. 5,600,000. While the Djikstra algorithm obtains a total cost of Rp.  7,200,000.  This  means  that  if  you  want  to  get  the  lowest  cost  in  designing  a  pipe installation  for  clean  water,  an  estimator  can  use  the  prim,  crucial  or  Floyd-Warshall algorithm.
Keywords: Plumbing, Prim Algorithm, Kruskal, Djikstra, Floyd-Warshall

## Jurnal Pendidikan Teknologi Informasi
18
Issn :2460-7274 E-Issn:26858177

## PENDAHULUAN
Perkembangan  ilmu  pengetahuan  dan teknologi  sampai  saat  ini  terus  mengalami peningkatan  yang  signifikan,  salah  satunya adalah  Ilmu  Teknik  Sipil  khususnya  Ilmu Plumbing,  yaitu  ilmu  yang  membahas  tentang teknologi  pemipaan  beserta  peralatannya untuk menyediakan air bersih, baik dalam sisi kualitas  maupun  kuantitas  (kontiniuitas)  yang memenuhi kriteria tertentu dan juga meliputi sistem pembuangan air bekas atau kotor dari suatu tempat tertentu untuk mencapai sebuah kondisi  yang  higienis  dan  nyaman.  Metode instalasi plumbing adalah suatu hal yang wajib seorang  kontraktor  ketahui,  karena  plumbing merupakan salah satu unsur terpenting dalam sebuah  bangunan.  Para  peneliti  terus melakukan penelitian untuk selalu memunculkan penemuan-penemuan baru yang dapat memberikan sumbangan ilmu pengetahuannya sebagai penunjang berkembangnya ilmu-ilmu lain. Pada penelitian sebelumnya  yang  dilakukan  oleh  Swaditya
Rizki dengan judul penelitian Penerapan Teori Graf  untuk  Menyelesaikan  Masalah  Minimum Spanning Tree (MST) Menggunakan Algoritma Kruskal,  di  dalam  penelitian  tersebut  peneliti memberikan suatu solusi untuk mendeskripsikan  permasalahan  transportasi dan  desain  jaringan  komunikasi  ke  dalam suatu  graf  lengkap  dengan  menggunakan Algoritma Kruskal [1].
Metode algoritma yang dapat digunakan dalam  pemecahan  masalah  yang  berkaitan dengan  bidang  teknik  sipil  tidak  hanya menggunakan  kruskal,  tetapi  algoritma  prim, djikstra,  atau  algoritma  yang  lain.  Tetapi dalam  penggunaannya  di  lapangan  sedikit, perencana  tidak  tertarik  menggunakan algoritma tersebut. Padahal dalam
menentukan  suatu  perencanaan  pelaksanaan pembuatan  suatu  proyek,  utamanya  pada perencanaan pemasangan pipa saluran air atau proyek  lainnya  dalam  bidang  teknik  sipil diperlukan  rencana  yang  baik,  agar  dalam
menentukan  biaya  operasional  atau  estimasi biaya  perencanaan  proyek  tersebut  tidak hanya  ditentukan  begitu  saja,  namun  dapat ditentukan  dengan  baik.  Hal  ini  dimaksudkan karena  estimasi  biaya  suatu  proyek merupakan  hal  yang  penting,  karena  bila terjadi  masalah  dalam  estimasi  biaya  maka dapat  memberikan  efek  negatif  pada  seluruh proses  konstruksi  dan  semua  pihak  yang terlibat dalam proyek tersebut. Sehingga perlu menggunakan  studi  yang  lebih  mendalam  lagi tentang penggunaan algoritma tersebut.
Maka  dalam  hal  ini  peneliti  tertarik untuk  menggunakan  algoritma  Prim,  Kruskal,
Djikstra, dan Floyd-Warshall untuk menyelesaikan  masalah  pohon  merentang minimum  pada  pemasangan  pipa  saluran  air dengan  meneliti  biaya  minimumnya.  Sehingga peniliti  bisa  mengetahui  algoritma  mana  dari ke-empat algoritma tersebut yang menghasilkan  biaya  terendah,  sebagai  tujuan akhir  dari  penelitian  ini  adalah  penerapannya di  lapangan  dari  salah  satu  algoritma  yang menghasilkan  biaya  minimum.  Sehingga pemasangan  pipa  saluran  air  dilakukan  secara sistematis  dan  cermat  agar  kebutuhan penghuni  bangunan  atas  air  dapat  terpenuhi dengan  baik  secara  kontinu.  Berikut  ini penjelasan dari beberapa jenis algoritma yang akan digunakan, yaitu:
a. Algoritma Prim
Algoritma  Prim  adalah  suatu  algoritma di  dalam  teori  graf  yang  bertujuan menemukan  Minimum  Spanning  Tree  untuk menghubungkan  graf  berbobot.  Ini  berarti algoritma  ini  menemukan  subset  dari  sebuah tepi  yang  membentuk  sebuah  Tree  yang meliputi  setiap  titik  nya.  Dimana  total  beban dari  setiap  tepi  di  Tree  diminimalkan.  Jika Graf  tidak  terhubung,  maka  ini  hanya  akan menemukan  sebuah  Minimum  Spanning  Tree menjadi  satu  jalur  untuk  komponen  yang terhubung.  Algoritma  ini  ditemukan  pada tahun  1930  oleh  seorang  ahli  matematika Vojtech  Jarnik,  dan  kemudian  dipublikasikan

## Jurnal Pendidikan Teknologi Informasi
19
Issn :2460-7274 E-Issn:26858177
oleh  seorang  computer  scientist  Robert  C. Prim pada tahun 1957 dan ditemukan kembali oleh  Dijkstra  pada  tahun  1959.  Oleh  karena itu  terkadang  Algoritma  ini  juga  disebut  DJP algorithm atau algoritma Jarnik [2].
Langkah-langkah algoritma Prim:
(1) Ambil  sisi  dari  graf  yang  berbobot minimum,  kemuadian  masukkan  ke  dalam pohon.
(2) Pilihlah  sisi  yang  mempunyai  bobot minimum  dan  bersisian  dengan  pohon. Namun  sisi  tersebut  tidak  membentuk sirkuit  di  dalam  pohon.  Masukkan  sisi tersebut ke dalam pohon.
(3) Ulangi langkah 2 sampai pohon merentang minimum  terbentuk,  pohon  merentang minimum  terbentuk  setelah  mengalami penggulangan  sebanyak  n-2  kali.  (n  adalah jumlah simpul graf). b. Algoritma Kruskal Algoritma Kruskal pertama kali dipopulaerkan  oleh  Joseph  Kruskal  pada tahun 1956. Algoritma Kruskal adalah sebuah algoritma  dalam  teori  graf  yang  mencari sebuah  Minimum  Sanning  Tree  untuk  sebuah graf  berbobot  yang  terhubung.  Ini  berarti mencari  subset  dari  sisi  yang  membentuk sebuah  Tree  yang  menampung  setiap  vertex, dimana  total  bobot  dari  semua  sisi  dalam Tree  adalah  minimum.  Jika  graf  tidak terhubung,  kemudian  ini  mencari  sebuah Minimum  Spanning  Forest  (sebuah  Minimum Spanning  Tree  untuk  tiap  komponen  yang terhubung).  Algoritma  Kruskal  adalah  suatu contoh dari Algoritma Greedy [2].
Langkah-langkah algoritma Kruskal:
(1) Lakukan pengurutan terhadap setiap sisi di graf  mulai  dari  sisi  dari  bobot  terkecil hingga bobot terbesar.
(2) Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit pada pohon, kemudian  tambahkan  sisi  tersebut  ke dalam pohon.
(3) Ulangi  langkah  kedua  sampai  pohon minimum  merentang  terbentuk,  pohon
merentang  minimum  terbentuk  setelah mengalami penggulangan sebanyak n-1 kali. (n adalah jumlah simpul graf).
c. Algoritma Djikstra
Algoritma  ini  dinamakan  sesuai  dengan nama  penemunya,  yaitu  seorang  ilmuwan komputer  berkebangsaan  Belanda  yang bernama  Edsger  Dijkstra.  Algoritma  Dijkstra merupakan  salah  satu  algoritma  yang  efektif dalam  memberikan  lintasan  terpendek  dari suatu  lokasi  ke  lokasi  yang  lain.  Prinsip  dari algoritma  Dijkstra  adalah  dengan  pencarian dua  lintasan  yang  paling  kecil.  Algoritma Dijkstra  memiliki  iterasi  untuk  mencari  titik yang  jaraknya  dari  titik  awal  adalah  paling pendek.  Pada  setiap  iterasi,  jarak  titik  yang diketahui  (dari  titik  awal)  diperbarui  bila ternyata  didapat  titik  yang  baru  yang memberikan jarak terpendek. Syarat algoritma  ini  adalah  bobot  sisinya  yang  harus non-negatif [3].
Pada  algoritma  dijkstra  pemecahan masalah  diperuntukkan  untuk  sebuah  Graph G=(V,E)  yang  berbobot  non  negatif. Diasumsikan  w(i,j)≥0  untuk  masing -masing edge (i,j) Є E.
Langkah-langkah algoritma Djikstra:
1) Inisialisasi s (sumber)
(a) Pilih salah satu vertex sebagai sumber
(b) Maka d(s) = 0
(c) Beri label 0 pada vertex s.
2) Untuk masing-masing edge  e Є E Jika i adalah endpoint dari e yang sudah diberi label dan j adalah endpoint yang belum diberi label maka p(i,j) adalah = d(i) + w(i,j)
3) e  adalah  edge  untuk  T  yang  mempunyai nilai P terkecil.
(a) Jika  i  adalah  endpoint  dari  e  yang  sudah diberi  label  dan  j  adalah  endpoint  yang belum diberi  label  maka  tambahkan e dan vertex j ke tree T
(b) d(j)=P(ij)
(c) Beri label d(j) pada vertex j
4) Kembali ke no 2

## Jurnal Pendidikan Teknologi Informasi
20
Issn :2460-7274
E-Issn:26858177
d. Floyd-Warshall Algoritma yang ditemukan oleh Warshall  dimana  algoritma  ini  menerapkan pemrograman  dinamis  yang  lebih  menjamin keberhasilan penemuan solusi optimum untuk kasus penentuan lintasanterpendek. Algoritmta Floyd-Warshall memiliki input graf yang beberapa titik (V) dan sisi (E). Sisi boleh berbobot  negatif,  namun tidak  diperbolehkan memiliki  siklus  negatif.  Algoritma  ini menghitung  bobot  terkecil  dari  semua  jalur dan  melakukan  sekaligus  untuk  semua  titik. Metode  ini  melakukan  pemecahan  masalah dengan  memandang  solusi  yang  akan diperoleh sebagai suatu keputusan yang saling terkait. Maksudnya solusi-solusi dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu [4].
Dalam  usaha  untuk  mencari  lintasan terpendek,  algoritma  ini  memulai  iterasi  dari titik  awalnya  kemudian  memperpanjang lintasan  dengan  mengevaluasi  titik  demi  titik hingga  mencapai  titik  tujuan  dengan  jumlah bobot  se-minimum  mungkin.  Misalkan  Wo adalah  matriks  hubung  graf  berlabel  mula- mula.  W*  adalah  matriks  hubung  minimal dengan wij* = lintasan terpendek dari titik vi ke  vj.  Langkah-langkah  algoritma  Floyd- Warshall  untuk  mencari  lintasan  terpendek sebagai berikut:
1) W = Wo
2) Untuk k = 1 hingga n, lakukan: Untuk i = l hingga n, lakukan:
Untuk j = l hingga n, lakukan:
Jika W(i, j) > W(i, k) + W(k, j) maka tukar
W(i,j) dengan W(i, k) + W(k, j)
3) W* = W

## METODOLOGI PENELITIAN
Metode penelitian yang akan digunakan adalah  kajian  pustaka  yakni  dengan  mengkaji literatur-literatur yang berkaitan dengan teori graf terkhusus pada masalah yang
berhubungan  pohon  rentang  minimum  dan
Algoritma  Prim,  Kruskal,  Djikstra  dan  Floyd- Warshal
HASIL DAN PEMBAHASAN Persoalan  pohon  merentang  minimum yaitu menentukan sisi-sisi yang menghubungkan  simpul-simpul  yang  ada  pada sumber  sehingga  diperoleh  panjang  sisi  total yang  minimum.  Maka  persoalan  pohon merentang minimum pertama pada pemasangan pipa air bersih adalah menentukan pola pemasangan pipa air dimana, pipa harus dihubungkan dari sumber air utama (pipa  induk)  ke  pengguna.  Namun  proses tersebut harus melalui sumber-sumber air.
Dimulai  dari  sumber  air  utama  (pipa induk)  yang  dihubungkan  ke  sumber  air,
kemudian dari sumbe air tersebut dihubungkan  ke  rumah-rumah  warga  atau perumahan,  dengan  jarak  yang  minimum dengan menggunakan algoritma Prim, Kruskal, Djikstra sehingga menghasilkan biaya pemasangan  yang  minimum.  Dari  kasus perancangan  pipa  saluran  air  yang  terjadi  di sebuah  Perumahan  “X”  maka  penulis  dapat menentukan biaya minimum pada pemasangan pipa  saluran  air  di  Perumahan  “X”  dengan menggunakan  algoritma  Prim,  Kruskal,  dan Djikstra.  Berikut  ini  merupakan  gambar  dari distribusi air pada pipa saluran air bersih:
A B C E D F G H I M K J

## Jurnal Pendidikan Teknologi Informasi
21
Issn :2460-7274 E-Issn:26858177
Gambar 1. Perancangan Instalasi Pipa Air Bersih Untuk  keterangan  titik,  jarak,  biaya  maupun bobot dapat dilihat dari tabel berikut ini . Tabel 1. Nilai Masing-Masing Titik No. Ket Jarak (m) Biaya/m Bobot 1 A – C 3 Rp. 160.000., 48 2 A – B 6 Rp. 160.000., 96 3 B – D 4 Rp. 160.000., 64 4 B – J 8 Rp. 160.000., 128 5 C – E 4 Rp. 320.000., 128 6 D – E 3 Rp. 160.000., 48 7 D – F 2 Rp. 160.000., 32 8 F – J 3 Rp. 160.000., 48 9 F – M 3 Rp. 160.000., 48 10 E – M 2 Rp. 325.000., 65 11 F – G 2 Rp. 160.000., 32 12 J – K 2 Rp. 325.000., 65 13 G – K 3 Rp. 160.000., 48 14 G – H 2 Rp. 160.000., 32 15 K – I 2 Rp. 325.000., 65 16 H – I 4 Rp. 160.000., 64 17 M - I 9 Rp. 160.000., 144 1. Algoritma Prim Berdasarkan  gambar  1  dan  tabel  1
diatas  maka  penyelesaian  kasus  Minimum Spanning  Tree  menggunakan  algoritma  prim, dapat dilihat dari gambar berikut ini.
Gambar 2. Hasil Akhir Algoritma Prim
Berdasarkan gambar 1 pohon merentang  minimum  diatas  dengan  total bobot 48 + 96 + 64 + 48 + 32 + 48 + 32 +
48  +  48  +  32  +  64  =  560,  Maka  biaya  yang digunakan  untuk  pemasangan  pipa  saluran  air bersih  di  perumahan  “X”  adalah  sebesar  Rp. 5.600.000,-.
5) Algoritma Kruskal
Berdasarkan  gambar  1  dan  tabel  1  maka penyelesaian  kasus  Minimum  Spanning  Tree menggunakan  algoritma  kruskal,  dapat  dilihat dari gambar berikut ini.
Gambar 3. Hasil Akhir Algoritma Kruskal
Berdasarkan  gambar  pohon  merentang minimum diatas dengan total bobot 48 + 96 + 64 + 48 + 32 + 48 + 32 + 48 + 48 + 32 + 64 =  560,  Maka  biaya  yang  digunakan  untuk pemasangan  pipa  saluran  air  bersih  di perumahan  “X”  adalah  sebesar  Rp. 5.600.000,-.
6) Algoritma Djikstra Berdasarkan gambar 1 dan tabel 1 maka penyelesaian  kasus  Minimum  Spanning  Tree menggunakan  algoritma  djikstra,  dapat  dilihat dari gambar berikut ini.
A B C D F M G J K H I E 96 48 64 48 48 32 48 48 32 32 64
A B C D F M G J K H I E 96 64 48 48 48 48 48 32 32 32 64

## Jurnal Pendidikan Teknologi Informasi
22
Issn :2460-7274 E-Issn:26858177
Gambar 4. Hasil Akhir Algoritma Djikstra
Berdasarkan  gambar  pohon  merentang minimum diatas dengan total bobot 48 + 128 + 96 + 64 + 32 + 48 + 32 + 48 + 32 + 64 + 128 = 720, Maka biaya yang digunakan untuk pemasangan  pipa  saluran  air  bersih  di perumahan  “X”  adalah  sebesar  Rp. 7.200.000,-.
7) Algoritma Floyd-Warshall
Berdasarkan gambar 1 dan tabel 1 maka penyelesaian  kasus  Minimum  Spanning  Tree menggunakan algoritma Floyd-Warshall untuk menentukan  biaya  minimum  dari  Titik  A  ke Titik I, dapat dilihat dari gambar berikut ini.
Gambar 5. Hasil Akhir Algoritma Floyd- Warshall Berdasarkan  gambar  pohon  merentang minimum diatas dengan total bobot 48 + 96 + 64 + 48 + 32 + 48 + 32 + 48 + 48 + 32 + 64 =  560,  Maka  biaya  yang  digunakan  untuk pemasangan  pipa  saluran  air  bersih  di perumahan  “X”  adalah  sebes ar  Rp. 5.600.000,-.
Berdasarkan  hasil  penelitian  pohon rentang  minimum  dari  jalur  distribusi  pipa saluran  air  bersih  di  Perumahan  “X” diperoleh hasil akhir, sebagai berikut:
Tabel 2. Hasil Ringkasan Hasil
Jenis Algoritma Biaya Prim Rp. 5.600.000,-. Djikstra Rp. 7.200.000,-. Kruskal Rp. 5.600.000,-. Floyd-Warshall Rp. 5.600.000,-. Hasil penelitian pohon rentang minimum dari  jalur  distribusi  pipa  saluran  air bersih di Perumahan “X” dengan menggunakan  algoritma  Prim,  Kruskal,  dan Floyd-Warshall diperoleh total biaya minimum  yang  sama  yaitu  sebesar  Rp. 5.600.000,-.  Sedangkan  algoritma  Djikstra memperoleh  total  biaya  sebesar  Rp.
A B C D F M G J K H I E 32 32 32 64 48 48 96 48 12 128 64 A B C D F M G J K H I E 96 48 64 48 48 32 48 48 32 32 64

## Jurnal Pendidikan Teknologi Informasi
23
Issn :2460-7274 E-Issn:26858177
7.200.000,-.  Itu  dikarenakan  keunggulan pohon  rentang  minimum  menggunakan algoritma Prim dan Kruskal, meskipun dengan cara  manual  tetapi  dapat  diketahui  sisi  mana saja  yang  terhapus,  sisi  mana  saja  yang  tidak terhapus,  dan  mengetahui  secara  langsung bagaimana pohon rentang minimumnya.
Walaupun  algoritma  Floyd-Warshall memperoleh  biaya  minimum  yang  sama dengan  prim  dan  kruskal,  tapi  dalam menyelesaikannya  membutuhkan  waktu  yang lama,  karena  algoritma  ini  menghitung  bobot terkecil  dari  semua  jalur  dan  melakukan sekaligus  untuk  semua  titik.  Sedangkan walaupun  algoritma  djikstra  menghasilkan biaya  yang  cukup  besar  dibandingkan  dengan algoritma  yang  lain,  tapi  dalam  waktu penyelesaiannya  lebih  cepat  dibandingkan algoritma yang lain.
Perlu  diperhatikan  juga  hasil  akhir  dari algoritma  Prim,  Kruskal,  dan  Floyd-Warshall yang menghasilkan biaya minimum yang sama, alasannya  adalah  gambar  instalasi  pipa  yang dirancang sangat sederhana, sehingga kompleksitasnya sedikit. Itu yang menyebabkan hasil akhir yang sama untuk tiga algoritma tersebut walaupun langkah
perhitungannya berbeda.
Bila  ingin  mendapatkan  biaya  yang paling  murah  dalam  merancang  instalasi  pipa untuk  air  bersih,  seorang  estimator  bisa menggunakan  algoritma  prim,  kruskal, ataupun Floyd-Warshall karena dalam proyek pembuatan
sebuah rumah ataupun
perumahan,  pekerjaan  plumbing  seperti  ini sangat  perlu  dan  penting,  karena  sebagai seorang  lulusan  teknik  sipil  harus  mampu menjadi  estimator  yang  baik  di  lapangan, sehingga  nanti  biaya  yang  akan  dikeluarkan dalam  proyek  pemasangan  pipa  bisa  ditekan se-minimal mungkin dengan bantuan algoritma.

## KESIMPULAN
Berikut  ini  kesimpulan  yang  dapat diambil  dari  analisis  perbandingan  algoritma prim, kruskal, dan djikstra untuk memecahkan pohon  merentang  minimum  studi  kasus perancangan  pemasangan  pipa  saluran  air bersih adalah:
1. Biaya  minimum  dalam  perancangan pemasangan  pipa  algoritma  Prim,  Kruskal, dan  Floyd-Warshall  adalah  sebesar  Rp. 5.600.000,-.  Sedangkan  algoritma  Djikstra memperoleh  total  biaya  sebesar  Rp.
7.200.000,-.
2. Algoritma  Prim,  Algoritma  Kruskal,  dan Algoritma Floyd-Warshall dapat menyelesaikan  masalah  pencarian  pohon merentang  minimum  dengan  biaya  yang paling  murah  dibandingkan  Algoritma
Djikstra.
3. Keunggulan  pohon  rentang  minimum menggunakan  algoritma  Prim dan  Kruskal, meskipun dengan cara manual tetapi dapat diketahui sisi mana saja yang terhapus, sisi mana  saja  yang  tidak  terhapus,  dan mengetahui  secara  langsung  bagaimana pohon rentang minimumnya.
4. Algoritma  Floyd-Warshall  memperoleh biaya  minimum  yang  sama  dengan  prim dan  kruskal,  tapi  dalam  menyelesaikannya membutuhkan  waktu  yang  lama,  karena algoritma  ini  menghitung  bobot  terkecil dari  semua  jalur  dan  melakukan  sekaligus untuk semua titik.
5. Algoritma  Djikstra  menghasilkan  biaya yang  cukup  besar  dibandingkan  dengan algoritma  yang  lain,  tapi  dalam  waktu penyelesaiannya  lebih  cepat  dibandingkan algoritma yang lain.
Dalam penelitian ini, penulis menggunakan  program  cara  manual  sebagai alat pembanding sekaligus untuk memvisualisasikan  hasil  pohon  rentang minimum.  Kelemahan  adalah  kemungkinan terjadi human error sangatlah besar Sehingga dalam  penelitian  ini  saran  yang  dapat

## Jurnal Pendidikan Teknologi Informasi
24
Issn :2460-7274 E-Issn:26858177
disampaikan adalah untuk penelitian-penelitian selanjutnya  yang  mengkaji  pohon  rentang minimum dapat mencoba software komputer guna  mempersingkat  waktu  dan  me- minimalisir  kesalahan,  selain  itu  dapat menambah  pengetahuan  tentang  software- software komputer yang dapat menyelesaikan permasalahan pohon rentang minimum.
Selain  itu  dalam  membuat  sebuah penelitian  yang  baru,  akan  lebih  baik  bila mendesain gambar lebih kompleks tidak hanya yang sederhana saja untuk menghitung dengan menggunakan  algoritma  MST,  karena  akan lebih  jelas  dalam  mengetahui  perbedaan masing-masing
algoritma, sehingga keterterapannya lebih baik.
Sedangkan  untuk  penerapan,  ini  masih terbatas  pada  pengaplikasian  teori  terhadap pendistribusian  pipa  saja  dengan  contoh  yang sederhana, sehingga diperoleh hasil yang sama dari  beberapa  algoritma  MST  yang  dipakai untuk itu dalam praktiknya diharapkan peneliti selanjutnya  bisa  mengkaji  lebih  dalam permasalahan-permasalahan  di  lapangan  yang lebih kompleks, sehingga hasil yang didapatkan lebih  memuaskan,  supaya  penerapan  yang digunakan  tidak  hanya  dikaji  secara  teori semata.

## DAFTAR PUSTAKA
S.  Rizki,  “Penerapan  Teori  Graf  Untuk Menyelesaikan  Masalah  Minimum Spanning  Tree  (Mst)  Menggunakan Algoritma  Kruskal,”  AKSIOMA  J. Math. Educ., vol. 1, no. 2, 2012.
H.  G.  Fadli,  “Studi  Minimum  Spanning  Tree dengan Algoritma Prim dan Kruskal,” J. Tek. Inform. Inst. Teknol. Bandung, 2006. D. Satyananda, “Struktur Data,” Malang, 2012. A. R. Hasibuan, I. Pendahuluan, A. Penerapan, and  B.  A.  F.  Warshall,  “Penerapan algoritma  floyd  warshall  untuk menentukan  jalur  terpendek  dalam pengiriman  barang,”  J.  Ris.  Kompu t., vol. 3, no. 6, pp. 20 – 24, 2016.
Putra  Chandra  Anugrah.  2019.  Perancangan Media Pembelajaran Berbasis Multimedia. 137.