Abstract
Dalam teori graf, masalah lintasan terpendek adalah permasalahan pencarian suatu lintasan antara dua simpul pada suatu graf sedemikian sehingga jumlahan bobot-bobot dari sisi-sisi dalam lintasan tersebut minimum. Algoritma Kruskal merupakan suatu algoritma yang digunakan untuk pencarian pohon pembangun minimum secara langsung berdasarkan algoritma pohon pembangun minimum yang umum. Pada algoritma Kruskal, sisi-sisi graf diurutkan berdasarkan bobot masing-masing dari yang terkecil sampai yang terbesar. Algoritma Kruskal menggunakan pendekatan Greedy yang memandang graf sebagai forest dan setiap simpul memiliki tree. Pencarian pohon pembangn minimum dengan algoritma Kruskal dapat diaplikasikan pada distribusi air bersih PDAM Kabupaten Lombok Utara. Dalam artikel ini, dibahas pencarian rute terpendek pada distribusi air PDAM Lombok UtaraReferences
- Munir, Rinaldi, 2010, Matematika Diskrit, Informatika Bandung, Bandung.
- Pratama, A. P., Sumarno, DEA, Darmaji. 2013. Penggunaan Algoritma Kruskal dalam Jaringan Pipa Air Minum Kecamatan Nganjuk Kabupaten Nganjuk. Institut Teknologi Sepuluh Nopember (ITS), Surabaya.
- Ismail, T., T. Setiadi. 2014. Media Pembelajaran Strategi Algoritma Pada Pokok Bahasan Pohon Merentang Minimum Dan Pencarian Lintasan Terpendek. Universitas Ahmad Dahlan, Yogyakarta.
- Nugraha, D. W., 2011. Aplikasi Algoritma Prim Untuk Menentukan Minimum Spanning Tree Suatu graf berbobot Dengan Menggunakan Pemrograman Berorientasi Objek. Univaersitas Tadulako, Palu.