In this post we introduce Prim’s algorithm to identify the Minimum Spanning Tree of a graph. The MST is a tree made up by the subset of edges from a weighted graph that connect every node while having the smallest total weight possible.
MSTs have a wide range of practical applications, specially in distribution networks where we must reach every node in the graph while minimizing the overall cost. As a test case, we apply Prim’s algorithm to an Open Street Map road network.
Prim’s Algorithm
Prim’s algorithm, despite its name, was originally introduced by V. Jarník in 1930 and eventually rediscovered independently by Robert Prim and Edsger W. Dijkstra in the late 50s.
The algorithm has some similarities with Dijkstra’s algorithm (that we discussed here) with a greedy procedure to iteratively grow the tree by adding one edge at a time.
Choose an arbitrary seed node.
At each step add the lightest edge that connects one of the nodes already in the tree to one of the nodes not yet added.
Stop w…
