Optimization of Clean Water Distribution Networks at the Unima FMIPA Campus Using the Minimum Spanning Tree Method
Abstract
The availability of clean water within higher education institutions is highly crucial to support the operations and convenience of the academic community. Issues regarding limited access to clean water were identified within the Faculty of Mathematics and Natural Sciences (FMIPA) at the State University of Manado, particularly in the Department of Mathematics Education. This study aims to model the clean water distribution network in FMIPA as a weighted graph and determine the optimal distribution path with minimum total pipe length using the Minimum Spanning Tree (MST) method via Prim’s Algorithm. This operations research-based quantitative study mapped six main nodes encompassing the water tank and departmental buildings. Distance data were obtained through digital map observations and Google Earth based on realistic piping pathways. The results indicate that optimization using Prim’s Algorithm produces an efficient single network configuration with the route: . This network successfully eliminates path redundancy, achieving a minimum total pipe length of 175 meters. Through this modeling, the Mathematics Education Department secures a reliable water supply delivered from the Science Education Building with a distance efficiency of only 25 meters. The implications of this research provide a practical recommendation for the university administration to efficiently optimize the allocation of plumbing material budgets.
References
Ahmed, E. O., Ali, A. I., & Balla, S. A. (2018). Robust water distribution system using minimal spanning tree algorithm. International Journal of Computer Applications, 158(1), 1–5. https://www.ijcaonline.org/archives/volume158/number1/26869-2017912724/
Chen, Y. (2023). The analysis and application of Prim algorithm, Kruskal algorithm, Boruvka algorithm. IOP Conference Series: Earth and Environmental Science. ResearchGate. https://www.researchgate.net/publication/381997773
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Faizah, S. Z., Kartika, D. L., & Winarni, A. (2025). Implementasi algoritma prim untuk optimasi panjang pipa pada sistem distribusi air bersih di Desa Banteran. Proximal: Jurnal Penelitian Matematika dan Pendidikan Matematika, 8(1), 431–441. https://doi.org/10.30605/proximal.v8i1.5353
Girsang, C. S., Sinaga, L. E., & Sembiring, R. W. (2019). Prim's algorithm to model the pipe network at the water supply company. IOP Conference Series: Journal of Physics: Conference Series, 1188(1), 012074. https://doi.org/10.1088/1742-6596/1188/1/012074
Kafaji, S. M. H. A., & Shiker, M. A. K. (2022). Optimizing the minimum spanning tree (MST) and its relationship with the minimum cut. International Journal of Health Sciences, 6(S6), 9347–9360. https://doi.org/10.53730/ijhs.v6nS6.12436
Mekonnen, M. M., & Hoekstra, A. Y. (2016). Four billion people facing severe water scarcity. Science Advances. DOI: 10.1126/sciadv.1500323
Mosbah, M., Arif, S., Mohammedi, R. D., & Hellal, A. (2017). Optimum distribution network reconfiguration using the MST algorithm. IEEE Conference.
Özkan, B., & Özceylan, E. (2018). Optimization of minimum spanning tree and traveling salesman problems arising in a university campus network. International Journal of Industrial Engineering and Operational Research, 1(1), 1–10. https://www.researchgate.net/publication/355144307
Rembulan, G. D., Luin, J. A., Julianto, V., & Septorino, G. (2020). Optimization of clean water pipeline network length in DKI Jakarta using the minimum spanning tree. Jurnal INTECH, 6(1), 75–87. https://doi.org/10.30656/intech.v6i1.2164
Rukmi, A. M., et al. (2025). ANE-MIST: Attributed network embedding with minimum spanning tree for optimizing water pipe network layouts. IEEE Access, 32. https://doi.org/10.1109/ACCESS.2025.3618792
Sari, R. F., Widyasari, R., & Marpaung, F. A. (2023). Optimization of the installation of clean water pipelines through minimum spanning tree with Prim algorithm. G-Tech: Jurnal Teknologi Terapan, 7(1), 70–74. https://doi.org/10.33379/gtech.v7i1.1819
Sembiring, R. R., Sufri, & Multahadah, C. (2022). Penerapan algoritma prim dalam menentukan minimum spanning tree (MST) (Studi kasus: Jaringan pipa PDAM Tirta Muaro Jambi). Jurnal Ilmiah Matematika dan Terapan, 19(1), 58–71. https://doi.org/10.22487/2540766X.2022.v19.11.15890
Taha, H. A. (2017). Operations Research: An Introduction (10th ed.). Pearson.
Wirakusuma, K. A., & Diatmika, K. D. (2025). Analisis perbandingan kompleksitas waktu algoritma MST dalam penyusunan jaringan pipa air bersih. Jurnal Teknologi dan Sistem Informasi Bisnis, 7(1), 172–179. https://doi.org/10.47233/jteksis.v7i1.1813
