Chapter 14 · Advanced Graphs
Shortest Paths+: Bellman–Ford and A*
When edges can be negative, relax every edge in rounds and use round |V| as an alarm for negative cycles. When you know roughly where the goal is, let a heuristic pull the search toward it.
Click a vertex, then another, to add that directed edge with the weight above (or re-weight it). Click an edge's weight label to delete the edge.
Draw on either grid. Both searches rerun instantly on the same map; press ▶ to watch them race.
Relaxation order · distances after each pass
How to read this
Bellman–Ford
- The number next to each vertex is its current estimate
d[v](∞ = not reached yet). The source has an orange ring. - Each pass relaxes every edge once, in the order shown in the chips. Yellow = the edge being checked; red = it improved
d[v]; green edges form the current shortest-path tree (pred). - After pass k, every vertex whose best path uses ≤ k edges is correct. A simple path has at most |V| − 1 edges, so |V| − 1 passes are enough, unless there is a negative cycle.
- Round |V| is the alarm: if any edge still relaxes, a negative cycle is reachable, and it is drawn in thick red.
A* vs Dijkstra
- Both grids show the same map; each move costs 1. Left: A* ranks cells by f = g + h. Right: Dijkstra ranks them by g alone (h = 0).
- Yellow cells were expanded (popped from the heap); the small number is f (A*) or g (Dijkstra). Blue cells sit in the heap (the frontier). Red is the cell being expanded now; green is the final path.
- Heap ties on f are broken toward larger g (deeper cells), as in the lesson, so A* commits to one route instead of flooding a plateau.
Try this
- Run the lesson graph (edge order c→d, a→d, a→c, b→c, b→a, s→a, s→b). It needs all 4 = |V| − 1 passes; final distances s 0, a 2, b 5, c 4, d 5. Press Lucky order (edges sorted along the final shortest-path tree): pass 1 already finds every final distance, and pass 2 changes nothing, so it stops early. Same graph, same answer, the order alone decides how many passes you need.
- Press Add d→b (−3). Before round |V|, predict whether it will fire. The cycle b → a → c → d → b has weight −3 + 2 + 1 − 3 = −3 and gets highlighted.
- Make a negative cycle that the source can't reach (e.g. edges
x y -2andy x 1). Bellman–Ford stays calm: unreachable cycles don't affect distances from s. - Grid: load the lesson grid. Both find a 13-step path, but Dijkstra expands 67 cells and A* only 21.
- Switch the heuristic to 2 × Manhattan and draw a U-shaped wall around the goal's side. Weighted A* expands even fewer cells, but can return a longer path than Dijkstra: the price of an inadmissible heuristic.