Another common goal in a weighted graph is to find the least expensive way to connect all the vertices together. Consider the graph below. It represents a number of buildings that we want to connect with fiber optic cable. We don’t care about how far it is from any particular building to any other particular building. We just want to make sure that all the buildings are connected together and that the total length of cable we need to use is as small as possible.
A collection of edges that connects all the vertices in a graph with as little cost as possible is known as a minimum spanning tree. To find a minimum spanning tree we can use Prim’s algorithm. It is almost identical to Dijkstra’s algorithm except that instead of tracking the cost to reach each vertex from the start vertex, it tracks the minimum cost to reach each vertex from any vertex in the tree that has already been built.
In Prim’s algorithm, we don’t worry about the cost involved in reaching the current vertex. We just care about the cost to reach the neighbor from the current vertex. So the cost function looks like this:
Prims(graph, start):
Map parentMap
Map costMap
Map knownMap
costMap[start] = 0
while costMap has a vertex that is not in knownMap:
select lowest cost vertex that is not in knownMap as minCostVertex
knownMap[minCostVertex] = true
for each neighbor in graph.getNeighbors(minCostVertex):
if neighbor not in knownMap:
costThroughVertex = graph.getEdgeWeight(minCostVertex, neighbor)
if (neighbor not in costMap) or (costThroughVertex < costMap[neighbor]):
costMap[neighbor] = costThroughVertex
parentMap[neighbor] = minCostVertex
return parentMap
In Prim’s algorithm, the starting vertex is less meaningful than in Dijkstra’s algorithm. Picking any vertex within a connected set of vertices of the graph will produce a minimum spanning tree for those vertices.
This animation shows a cost table instead of a priority queue. Each time it needs to select the next vertex to visit, it will scan the cost table to find the vertex with the lowest cost that has not yet been visited. Making that table into a priority queue would make
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
It calculates the cost of a vertex B being considered from vertex A as the weight of the edge connecting them plus the cost from the starting vertex to vertex A
It finds a minimal spanning tree for the reachable vertices from the start vertex
It finds a shortest path from one vertex to all other reachable vertices
the cost of a vertex B being considered from vertex A as the weight of the edge connecting them
