The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Shortest Path Algorithms

Next ►
►

BFS gave us the path with the fewest edges, but counting edges is like measuring a trip in number of roads instead of kilometers. As soon as every edge carries a weight — in TaskFlow, the hours or cost of the transition between two tasks — "fewer hops" no longer means "cheaper". This lesson presents the three classic shortest-path algorithms: Dijkstra (the workhorse, built on module 4's heapq: the course's flagship reuse), Bellman-Ford (slower but tolerant of negative weights), and Floyd-Warshall (all pairs). We keep working on the Graph class, which has been storing weights since 07-02 without us using them.

Contents

  1. Weighted graphs in TaskFlow
  2. Why BFS isn't enough with weights
  3. Dijkstra: the idea and its priority queue
  4. Full implementation with predecessors
  5. Step-by-step trace with a distance table
  6. Dijkstra's limitation: negative weights
  7. Bellman-Ford: idea and compact code
  8. Floyd-Warshall: all pairs (a mention)
  9. Comparison table and how to choose

Weighted graphs in TaskFlow

Picture the planning between two project milestones: from the start milestone to launch there are alternative routes (build a prototype or go straight to design, exit through the API or through the UI), and every transition has a cost in hours. The team wants the cheapest route between the two milestones:

plan = Graph(directed=True)
plan.add_edge("start", "design", 4)
plan.add_edge("start", "prototype", 2)
plan.add_edge("prototype", "design", 1)
plan.add_edge("prototype", "ui", 8)
plan.add_edge("design", "ui", 3)
plan.add_edge("design", "api", 5)
plan.add_edge("api", "launch", 2)
plan.add_edge("ui", "launch", 2)
graph LR
    I[start] -->|4| D[design]
    I -->|2| P[prototype]
    P -->|1| D
    P -->|8| U[ui]
    D -->|3| U
    D -->|5| A[api]
    A -->|2| L[launch]
    U -->|2| L

Why BFS isn't enough with weights

BFS would say the best start → launch path is any 3-edge one, for example start → design → api → launch, with a real cost of 4 + 5 + 2 = 11 hours. But the 4-edge path start → prototype → design → ui → launch costs 2 + 1 + 3 + 2 = 8 hours: more hops, lower cost. BFS optimizes the number of edges because it processes vertices in layers; with weights, the layer says nothing about cost. We need to process vertices by accumulated cost, not by distance in hops. And what structure always hands over "the smallest value first"? Module 4's priority queue.

Dijkstra: the idea and its priority queue

Dijkstra maintains, for every vertex, the best known distance from the source, and repeats a greedy loop:

  1. Take the unclosed vertex with the smallest known distance (the heap provides it in O(log n)).
  2. Close it: its distance is now final.
  3. Relax its edges: for each neighbor, if going through the just-closed vertex improves its distance, record the improvement (and the predecessor).

Why can it "close" so confidently? Because if all weights are ≥ 0, any other path to that vertex would go through farther vertices and can no longer improve it. This is exactly the assumption that breaks with negative weights, as we'll see.

Instead of a "decrease key" operation (which heapq doesn't offer), we use the standard trick: insert duplicate entries and discard the stale ones on extraction — the same (priority, payload) tuple philosophy as module 4's UrgentInbox.

Full implementation with predecessors

import heapq

def dijkstra(graph, source):
    """Minimum distances from source and predecessors to rebuild paths."""
    distances = {v: float("inf") for v in graph.vertices()}
    distances[source] = 0
    predecessor = {source: None}
    heap = [(0, source)]                 # (distance, vertex) tuples, module 4
    closed = set()

    while heap:
        dist, current = heapq.heappop(heap)       # cheapest known
        if current in closed:
            continue                     # stale entry: already closed earlier
        closed.add(current)
        for neighbor, weight in graph.neighbors(current).items():
            new_dist = dist + weight
            if new_dist < distances[neighbor]:    # does 'current' improve it?
                distances[neighbor] = new_dist
                predecessor[neighbor] = current
                heapq.heappush(heap, (new_dist, neighbor))
    return distances, predecessor

def rebuild_path(predecessor, target):
    """Follows the predecessors backward and flips the result at the end."""
    if target not in predecessor:
        return None                      # unreachable from the source
    path = []
    while target is not None:
        path.append(target)
        target = predecessor[target]
    return path[::-1]

distances, predecessor = dijkstra(plan, "start")
print(distances["launch"])                          # 8
print(rebuild_path(predecessor, "launch"))
# ['start', 'prototype', 'design', 'ui', 'launch']

Key points in the code:

  • distances starts at infinity (float("inf")) except for the source: "I don't know a path yet". Any unreachable vertex ends the algorithm at infinity.
  • The if current in closed: continue is the duplicate discard: a vertex can sit in the heap several times with different distances; only the first extraction (the smallest) counts.
  • predecessor[v] stores where v was reached from along the best path; rebuild_path walks it backward — that's why the list must be reversed at the end ([::-1]), just like when we emptied a stack in module 3.
  • Cost: every edge can push one entry onto the heap, so O((n + a) · log n) — for sparse graphs, nearly linear.

Step-by-step trace with a distance table

Each row shows the vertex being closed and the distances after relaxing its edges (improvements in bold):

Closed start prototype design ui api launch
(initial) 0 inf inf inf inf inf
start (0) 0 2 4 inf inf inf
prototype (2) 0 2 3 10 inf inf
design (3) 0 2 3 6 8 inf
ui (6) 0 2 3 6 8 8
api (8) 0 2 3 6 8 8
launch (8) — — — — — —

Reading the key moments:

  • When prototype closes, design's distance improves from 4 to 3: the indirect route start → prototype → design (2+1) beats the direct one (4). design's predecessor switches from start to prototype. This is relaxation in action.
  • When design closes, ui improves from 10 (via prototype) to 6 (via design).
  • launch settles at 8 via ui; when api closes later, its offer (8 + 2 = 10) no longer improves anything.
  • Stale entries remain in the heap — (4, design), (10, ui), (10, launch) — which the continue discards as they surface.

Dijkstra's limitation: negative weights

Dijkstra closes vertices assuming that moving farther away never gets cheaper. With a negative edge, that logic breaks: a path that first "moves away" could later claw back cost and beat the one we declared final — but the vertex is already closed and never revisited. The result: wrong answers with no warning whatsoever, the worst kind of error.

Negative weights in real life? In TaskFlow they could model transitions that save effort (reusing finished work: doing B right after A knocks hours off); in finance, profitable operations; in logistics, subsidized legs. When they exist, the honest algorithm is Bellman-Ford.

Bellman-Ford: idea and compact code

Bellman-Ford gives up the heap's cleverness and applies orderly brute force: relax all edges, n − 1 times. After pass k, every shortest-path distance using ≤ k edges is correct; since no simple path has more than n − 1, that's enough. And it throws in something Dijkstra can't: if an extra pass still improves something, there is a negative-weight cycle (a loop that keeps getting cheaper forever, at which point "shortest path" stops making sense).

def bellman_ford(graph, source):
    # edge list (the third representation, mentioned in 07-02)
    edges = [(u, v, w) for u in graph.vertices()
                        for v, w in graph.neighbors(u).items()]
    distances = {v: float("inf") for v in graph.vertices()}
    distances[source] = 0
    predecessor = {source: None}

    for _ in range(len(distances) - 1):      # n - 1 passes
        changed = False
        for u, v, w in edges:                # relax ALL edges
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w
                predecessor[v] = u
                changed = True
        if not changed:                      # nothing improves: stop early
            break

    for u, v, w in edges:                    # extra pass: still improving?
        if distances[u] + w < distances[v]:
            raise ValueError("Negative-weight cycle: no shortest paths exist")
    return distances, predecessor

Cost: O(n · a) — noticeably worse than Dijkstra, and that's the deal: robustness in exchange for speed. Notice that it reuses rebuild_path as is: the interface (distances + predecessors) is the same.

Floyd-Warshall: all pairs (a mention)

When the question isn't "from this source" but "between all pairs" (a cost table from any milestone to any milestone), the reference algorithm is Floyd-Warshall: dynamic programming over the distance matrix, trying every vertex k as an intermediate stop:

# sketch: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all k, i, j
Trait Value
Result n × n matrix of all-pairs distances
Cost O(n³) time, O(n²) space
Negative weights Yes (without negative cycles; detects them on the diagonal)
Natural representation Adjacency matrix — its comeback announced in 07-02

Three nested loops and one relaxation line: probably the shortest algorithm in the course relative to the result it produces. It only pays off with small graphs or when you genuinely need the full table; we won't develop it further.

Comparison table and how to choose

Dijkstra Bellman-Ford Floyd-Warshall
Question 1 source → all 1 source → all all → all
Cost O((n + a) log n) O(n · a) O(n³)
Negative weights No Yes Yes
Detects negative cycles No Yes Yes
Supporting structure heapq (module 4) Edge list Matrix (07-02)
Use it when... Weights ≥ 0 (the normal case) Weights may be negative Small graph, full table

Rule of thumb: Dijkstra by default; Bellman-Ford if weights can be negative; Floyd-Warshall if you need the full matrix and n is modest (hundreds, not hundreds of thousands).

Common Mistakes and Tips

  • Running Dijkstra with negative weights. It doesn't fail or warn: it simply returns wrong distances. If your weights can be negative, validate first or switch algorithms.
  • Forgetting the stale-entry discard (if current in closed: continue). The algorithm would relax already-closed vertices from old heap entries: results sometimes right, sometimes wrong — the worst kind of bug.
  • Pushing non-comparable tuples onto the heap. If you pushed task dicts instead of ids, heapq would fail when breaking ties between tuples with equal distance. It's exactly the problem we solved in module 4 with (priority, counter, task); here the ids (strings) are comparable and (distance, id) suffices.
  • Rebuilding the path and forgetting to reverse it: predecessors are walked from target to source; without the final [::-1], the path comes out backwards.
  • Confusing "no path" with "a huge distance": check distances[v] == float("inf") explicitly before using the value.
  • Tip: always keep the predecessors. The distance says how much it costs; the rebuilt path says what to do, and in a real application (TaskFlow included) that's what the user wants to see.

Exercises

Exercise 1: reading Dijkstra's results

With distances and predecessor computed on plan from start: (a) what is the cheapest route to api and its cost? (b) Add the edge plan.add_edge("prototype", "api", 4) and reason (without running anything) how api's distance and predecessor change.

Exercise 2: cost of a specific route

Write path_cost(graph, path) returning the total cost of a list of consecutive vertices, or None if some leg doesn't exist as an edge. Compare the cost of ["start", "design", "api", "launch"] with Dijkstra's optimum.

Exercise 3: a dangerous discount

Suppose doing ui right after api reuses components: edge api → ui with weight −4. (a) Is Dijkstra still valid? (b) Run Bellman-Ford mentally: does launch's distance change? (c) What would happen if the discount were ui → prototype with weight −7?

Solutions

Solution 1:

  • (a) rebuild_path(predecessor, "api") → ['start', 'prototype', 'design', 'api'], cost 2 + 1 + 5 = 8. Notice that it shares a prefix with the route to launch: the shortest paths from one source form a tree (the shortest-path tree), another reunion with module 6.
  • (b) The new offer for api would be 2 + 4 = 6 < 8: when prototype closes, api would settle at 6 with predecessor prototype. Also, launch would receive the offer 6 + 2 = 8: the same total cost by another route; since 8 is not less than 8, the relaxation doesn't change the predecessor and the route via ui is kept.

Solution 2:

def path_cost(graph, path):
    total = 0
    for source, target in zip(path, path[1:]):   # consecutive pairs
        if not graph.edge_exists(source, target):
            return None
        total += graph.neighbors(source)[target]
    return total

print(path_cost(plan, ["start", "design", "api", "launch"]))  # 11
print(distances["launch"])                                    # 8

zip(path, path[1:]) pairs each vertex with the next: the idiomatic way to walk the legs. The "direct" route costs 11 against the optimum of 8: 37% more expensive for saving one edge.

Solution 3:

  • (a) No: with a negative edge in the graph, Dijkstra's closing guarantee vanishes (even if it happens to get some specific case right, it's no longer reliable).
  • (b) With api → ui = −4: reaching ui via api costs 8 + (−4) = 4 < 6, and then launch drops to 4 + 2 = 6. Bellman-Ford finds it in successive passes; the answer changes from 8 to 6, with route start → prototype → design → api → ui → launch.
  • (c) ui → prototype = −7 would create the cycle prototype → design → ui → prototype of weight 1 + 3 − 7 = −3: every lap "saves" 3 hours, distances would fall without a floor, and Bellman-Ford would raise the negative-cycle ValueError. A good reminder that a model with unlimited discounts is a badly posed model.

Conclusion

With weights on the edges, BFS hands the baton to Dijkstra: module 4's heapq priority queue always delivers the cheapest vertex, relaxation improves distances and predecessors, and rebuild_path turns the result into an actionable route — all in O((n + a) log n). Bellman-Ford covers the ground Dijkstra can't tread (negative weights, negative cycles) at the price of O(n · a), and Floyd-Warshall answers all-pairs in O(n³). So far we've always minimized the cost of one route between two points. The next lesson changes the question: not going from A to B, but connecting all the points together at minimum total cost — the minimum spanning tree, where undirected graphs make their comeback, along with Prim (almost a Dijkstra in disguise) and a brand-new structure: Union-Find.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved