Path versus spanning-tree objectives

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

Choose the objective before choosing the algorithm. Shortest path optimizes one route or many source routes; MST optimizes a network connecting everyone. Directed arborescences are another problem, not ordinary undirected MST.

Work through an example

The lab triangle's MST A-B-C costs 4, but shortest A-C uses weight 3. A shortest-path tree can also have greater total network weight than an MST.

Time and space complexity

BFS for equal weights, Dijkstra for nonnegative weights, Bellman-Ford for negative edges, MST methods for undirected connection cost.

Why it works

Correctness claims apply only to the stated objective and edge assumptions.

Common mistakes

An MST path is not guaranteed cheapest.
Ordinary Prim/Kruskal do not solve directed spanning objectives.

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.