ANALISIS PENYELESAIAN MASALAH TRANSPORTASI UNTUK MENENTUKAN SOLUSI OPTIMAL MELALUI PENDEKATAN MINIMUM SPANNING TREE (MST) DENGAN ALGORITMA KRUSKAL DAN PRIM

Abstract

This study aims to solve transportation problems by applying the Minimum Spanning Tree (MST) approach using two primary algorithms, namely Kruskal’s algorithm and Prim’s algorithm, to obtain an optimal solution. Both algorithms are part of graph theory and are used to determine the minimum spanning structure of a connected network. The Kruskal algorithm begins by sorting the edge weights in ascending order and then selecting the smallest edges sequentially until all vertices are connected without forming a cycle. In contrast, Prim’s algorithm starts by selecting an arbitrary initial vertex and then repeatedly adding the edge with the smallest cost that connects a new vertex to the growing tree. In the context of transportation problems, both algorithms are employed to minimize the total distribution cost based on the relationship between supply sources and demand destinations. The results of the study indicate that the MST approach using Prim’s algorithm performs more efficiently than Kruskal’s algorithm in terms of achieving a lower optimal solution value and requiring fewer iterations. Therefore, Prim’s algorithm can be recommended as a more effective method for optimizing transportation problems based on tree graph structures