Description

Prim's is used to construct a minimum spanning tree, which is the smallest tree that touches all nodes in the graph. It is the same as Dijkstra's Algorithm but with no target value.

Reach for when

You need to connect every node with the least total edge weight — a minimum spanning tree (e.g. cheapest cabling / roads / pipes linking all points). Not for distances between nodes — that's Dijkstra's Algorithm.

Runtime

O((V + E) log V) with a min-heap (O(V²) with an array)

Visualization

Minimum spanning tree:

Pseudocode

Add (0, start) to a min-heap
mstWeight = 0
While the heap is not empty:
	pop the (weight, node) with the smallest weight
	if node is already explored: continue
	mark node explored
	mstWeight += weight
	for each neighbor with edge cost:
		if neighbor is unexplored:
			push (cost, neighbor)
When the heap empties, every reachable node is in the tree → mstWeight is the total.

Code

import heapq

def prim(start, graph):
    explored = set()
    heap = [(0, start)]
    mst_weight = 0

    while heap:
        weight, node = heapq.heappop(heap)
        if node in explored:
            continue
        explored.add(node)
        mst_weight += weight

        for nxt, cost in graph[node].neighbors:
            if nxt not in explored:
                heapq.heappush(heap, (cost, nxt))

    return mst_weight