Shortest Paths

Interactive visualizations for Chapter 10 of the Ricerca Operativa notes

The Graph

We work with a directed weighted graph of 7 nodes and 11 arcs throughout this chapter.

Nodes: s, a, b, c, d, e, t
Arcs (with weights): s→a(4), s→b(2), a→c(5), a→d(1), b→a(8), b→d(3), c→e(3), c→d(2), d→e(6), d→t(9), e→t(1)

Dijkstra Algorithm Trace

Dijkstra’s algorithm maintains a priority queue ordered by tentative distance. At each step it extracts the minimum-distance unsettled node, relaxes its outgoing arcs, and moves the node to the settled set T.

Step	Extract	Process	Updates	Settled T after
0	s (d=0)	—	d[a]=4, d[b]=2	{s}
1	b (d=2)	b	d[d]=5; d[a] stays 4	{s, b}
2	a (d=4)	a	d[c]=9; d[d]=min(5,5)=5	{s, b, a}
3	d (d=5)	d	d[e]=11, d[t]=14	{s, b, a, d}
4	c (d=9)	c	d[e]=min(11,12)=11; d[d] stays 5	{s, b, a, d, c}
5	e (d=11)	e	d[t]=min(14,12)=12	{s, b, a, d, c, e}
6	t (d=12)	t	—	{s, b, a, d, c, e, t}

viewof step_dijkstra = Inputs.range([0, 7], {value: 0, step: 1, label: "Step Dijkstra:"})

Priority Queue Evolution

The chart below shows how the tentative distance d[v] evolves for each node across iterations, and the step at which each node is finalized (extracted from the priority queue).

Shortest Path Tree

After Dijkstra terminates, the predecessor pointers form the shortest-path tree rooted at s. The optimal path from s to t is highlighted in orange.

Predecessor map: pred[a]=s, pred[b]=s, pred[c]=a, pred[d]=b, pred[e]=d, pred[t]=e

Optimal Path Walkthrough

The shortest path from s to t has total cost 12, following s → b → d → e → t.

Why Non-Negative Weights Matter

Dijkstra’s algorithm relies on the greedy correctness property: once a node is settled, its distance cannot decrease further. This holds only when all arc weights are non-negative.

If a negative arc exists, a later path through an unsettled node might yield a smaller distance to an already-settled node — breaking the algorithm’s guarantee.

Counterexample: s→a(2), s→b(5), b→a(−4)

Dijkstra settles a first with d[a]=2 (via s→a).
But the true shortest path is s→b→a with cost 5+(−4)=1.
Dijkstra gives the wrong answer d[a]=2 instead of 1.

Key takeaway: For graphs with negative arc weights, use the Bellman–Ford algorithm (\(O(VE)\)), which handles negative weights but not negative cycles. Dijkstra remains the algorithm of choice when all weights are non-negative, running in \(O((V + E) \log V)\) with a binary heap.

Bellman-Ford Algorithm

For graphs with negative arc weights, Dijkstra’s algorithm’s greedy guarantee fails. The Bellman–Ford algorithm solves the Single-Source Shortest Paths (SSSP) problem in the presence of negative edge weights (but no negative cycles) in \(O(V E)\) time.

It performs \(n-1\) full passes over all \(m\) arcs, relaxing them. An optional \(n\)-th pass can be performed to detect negative cycles: if any distance decreases during the \(n\)-th pass, there is a negative cycle reachable from the source.

Choose a graph scenario, and use the slider to step through the relaxation passes (including the \(n\)-th check pass).

viewof bfGraph = Inputs.select(
  ["Graph A (Negative arc, no cycle)", "Graph B (With negative cycle)"],
  { label: "Graph Scenario:" }
)

viewof bfStep = Inputs.range([0, 4], { step: 1, value: 0, label: "Pass (Iteration):" })

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm solves the All-Pairs Shortest Paths (APSP) problem in \(O(n^3)\) time using dynamic programming. It operates on a weight matrix, progressively allowing vertices \(\{1, 2, \ldots, k\}\) to act as intermediate hops.

At each step \(k\), we update the shortest distance between every pair \((i, j)\): \[D^{(k)}[i][j] = \min \left( D^{(k-1)}[i][j], \; D^{(k-1)}[i][k] + D^{(k-1)}[k][j] \right)\]

Use the slider below to select \(k\) and observe how the distance matrix \(D^{(k)}\) updates. The active intermediate vertex \(k\) is highlighted in gold.

viewof fwStep = Inputs.range([0, 4], { step: 1, value: 0, label: "Intermediate Vertex k:" })