Abstract

Algoritma Dijkstra adalah algoritma dalam teori graf yang dapat digunakan untuk mencari jarak dan lintasan terpendek untuk sebuah graf terhubung berbobot. Kemudian algoritma Prim adalah algoritma yang dapat digunakan untuk mencari pohon rentang minimal untuk graf berbobot. Permasalahan dalam penulisan skripsi ini adalah bagaimana hasil lintasan terpendek menggunakan algoritma Dijkstra dan software TORA, danĀ  bagaimana hasil pohon rentang minimal menggunakan algoritma Prim dan software TORA. Dari data sekunder yang diperoleh dapat disusun gambar jaringan. Selanjutnya dari gambar jaringan dapat diperoleh jarak dan lintasan terpendek dengan menggunakan algoritma Dijkstra, pohon rentang minimal menggunakan algoritma Prim, dan bantuan software TORA. Berdasarkan hasil penelitian dan pembahasan dapat disimpulkan bahwa lintasan terpendek dari v1 (PDAM) ke v98 (titik penyambungan pipa terjauh) menggunakan algoritma Dijkstra dan software TORA adalah 7.792 m. Pohon rentang minimal menggunakan algoritma Prim dan software TORA ternyata 52.626 m. Hal ini mengakibatkan penghematan pipa pendistribusian sepanjang 20.644 m dari panjang total sebelumnya 73.270 m.