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

Abstract

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.