Minimum spanning trees

What is a weighted graph?

A weighted graph attaches a number to each edge, such as a distance, cost, or travel time. A path is a sequence of connected edges; its total cost is the sum of their weights. A shortest-path algorithm finds the least total cost under the problem’s rules. Different rules, especially negative weights, require different algorithms.

Example: A → B costs 4 and B → C costs 3, so that route costs 7. If A → C costs 10, the route through B is cheaper even though it uses more edges.

Helpful before this chapter

If these ideas are new, begin with:

Heaps and priority queues Graph representations and traversal Graph ordering and connectivity

Understand the idea

A spanning tree connects all vertices of an undirected connected graph with V-1 edges and no cycle. An MST minimizes the sum of those selected edge weights. Disconnected input has a minimum spanning forest instead.

Work through an example

Triangle edges A-B=2,B-C=2,A-C=3 have MST cost 4 using the two weight-2 edges. The direct A-C edge is a shorter route than the MST's A-B-C route.

Time and space complexity

Typical MST O(E log E) or O(E log V), with O(V+E) graph/storage needs.

Why it works

The selected edges remain acyclic and eventually connect all vertices if the graph is connected.

Common mistakes

Negative weights are allowed for MST.
A disconnected forest is not a spanning tree.

Chapter lab · Python implementation

Weighted objectives require precise distinctions. Dijkstra finds cheapest routes from one source with nonnegative weights. Bellman-Ford permits negative edges and detects reachable negative cycles. A minimum spanning tree minimizes the total edges needed to connect all vertices; it does not minimize every source-to-vertex route.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

import heapq

def dijkstra(graph,start):
    if any(w<0 for edges in graph.values() for _,w in edges):
        raise ValueError('nonnegative weights required')
    distances={start:0}; heap=[(0,start)]
    while heap:
        cost,node=heapq.heappop(heap)
        if cost!=distances[node]: continue
        for neighbor,weight in graph.get(node,[]):
            candidate=cost+weight
            if candidate<distances.get(neighbor,float('inf')):
                distances[neighbor]=candidate
                heapq.heappush(heap,(candidate,neighbor))
    return distances

def bellman_ford(n,edges,start):
    d=[float('inf')]*n; d[start]=0
    for _ in range(n-1):
        changed=False
        for a,b,w in edges:
            if d[a]!=float('inf') and d[a]+w<d[b]:
                d[b]=d[a]+w; changed=True
        if not changed: break
    if any(d[a]!=float('inf') and d[a]+w<d[b] for a,b,w in edges):
        raise ValueError('reachable negative cycle')
    return d

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':[('B',4),('C',1)],'C':[('B',2)],'B':[]}
assert dijkstra(g,'A')=={'A':0,'B':3,'C':1}
assert bellman_ford(3,[(0,1,4),(0,2,1),(2,1,-2)],0)==[0,-1,1]
try: bellman_ford(2,[(0,1,-1),(1,0,-1)],0)
except ValueError: pass
else: raise AssertionError('negative cycle not detected')

CHECK YOUR UNDERSTANDING

What is a weighted graph?

Initialize source A.