Exercises: Weighted Graphs and Shortest Paths

DataField.Dev

Exercises: Weighted Graphs and Shortest Paths

These build from mechanical traces to full proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek.

Several problems reuse the chapter's road map. For reference, here it is again as an adjacency list of (neighbor, weight) pairs:

adj = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1), ("E", 7)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}

Part A — Warm-ups: hand-trace and compute (⭐)

29.1 † On the road map above, write out all four simple directed paths from A to E and the weight of each. Which is the shortest, and what is $\delta(A, E)$?

29.2 Perform a single relaxation by hand. Suppose dist[u] = 5, dist[v] = 9, and the edge $(u, v)$ has weight $w = 3$. Does relaxation change dist[v]? Now repeat with $w = 6$. State the rule you used.

29.3 † Run Dijkstra from B on the road map. Give the round-by-round table (which vertex you finalize and the dist values after each round), and report $\delta(B, E)$.

29.4 A graph has vertices $\{s, a, b, c\}$ and edges $s \to a:2$, $s \to b:5$, $a \to b:1$, $a \to c:7$, $b \to c:3$. Find $\delta(s, c)$ and a shortest path achieving it, by inspection.

29.5 † For the road map, give the predecessor array prev produced by Dijkstra from A (the shortest-path tree). Then reconstruct the shortest path to D by following predecessors.

29.6 A graph with unit weights (every edge has weight $1$) is run through both BFS-from-$s$ and Dijkstra-from-$s$. Will the two return the same distances? Explain in one sentence, citing the special case noted in §29.1.

Part B — Prove it (with scaffolding) (⭐⭐)

29.7 † (Scaffolded — fill in the missing steps.) Prove the safety of relaxation: at every moment of any of this chapter's algorithms, $\text{dist}[v] \ge \delta(s, v)$ for every vertex $v$. Argue by induction on the number of relaxations performed.

Base case (0 relaxations). Initially $\text{dist}[s] = 0 = \underline{\hphantom{xxxx}}$ and $\text{dist}[v] = \infty \ge \delta(s, v)$ for $v \ne s$. So the claim holds before any relaxation.
Inductive step. Assume $\text{dist}[u] \ge \delta(s, u)$ and $\text{dist}[v] \ge \delta(s, v)$ for all vertices just before a relaxation of edge $(u, v)$. The relaxation can only change $\text{dist}[v]$, and only to the value $\underline{\hphantom{xxxxxx}}$. By the hypothesis, $\text{dist}[u] + w(u, v) \ge \delta(s, u) + w(u, v)$. But $\delta(s, u) + w(u, v)$ is the weight of some path to $v$ (a shortest path to $u$ then the edge $(u,v)$), so it is $\underline{\hphantom{xx}}$ than or equal to $\delta(s, v)$. Hence the new $\text{dist}[v] \ge \delta(s, v)$, and no other distance changed. $\blacksquare$

29.8 Prove that in a graph with no negative-weight cycle, some shortest path from $s$ to any reachable $v$ is simple (it repeats no vertex). (Hint: if a shortest path repeated a vertex, the loop between the two visits is a cycle; what does its weight have to be, and what can you remove?)

29.9 † (Scaffolded — fill the gap.) Recall the path-relaxation property (§29.4): after $k$ passes of relaxing all edges, $\text{dist}[v] = \delta(s, v)$ for every $v$ whose shortest path uses at most $k$ edges. Complete the inductive step. Assume the property after $k-1$ passes. Let $v$ have a shortest path $s = v_0, v_1, \dots, v_k = v$ using exactly $k$ edges, and let $u = v_{k-1}$.

The prefix $s, \dots, u$ is a shortest path to $u$ using $\underline{\hphantom{xx}}$ edges, so by the inductive hypothesis, after $k-1$ passes $\text{dist}[u] = \underline{\hphantom{xxxx}}$.
Pass $k$ relaxes every edge, including $(u, v)$, so afterward $\text{dist}[v] \le \text{dist}[u] + w(u, v) = \delta(s, u) + w(u, v) = \underline{\hphantom{xxxx}}$.
Combined with the safety of relaxation ($\text{dist}[v] \ge \delta(s, v)$), we conclude $\text{dist}[v] = \underline{\hphantom{xxxx}}$. $\blacksquare$

29.10 Prove that any shortest path is itself made of shortest paths: if $p = s, \dots, x, \dots, v$ is a shortest path from $s$ to $v$ and $x$ lies on it, then the prefix $s, \dots, x$ is a shortest path from $s$ to $x$. (This is the optimal-substructure fact the chapter uses repeatedly. Argue by contradiction: a cheaper prefix would give a cheaper whole path.)

29.11 † Prove that on a graph with non-negative weights, the order in which Dijkstra finalizes vertices is non-decreasing in distance: if $u$ is finalized before $v$, then $\delta(s, u) \le \delta(s, v)$. (Use the correctness theorem of §29.3 and the extract-min rule.)

29.12 Prove that adding the same positive constant $c$ to every edge weight can change which path is shortest. Concretely, exhibit a small graph and a value of $c$ such that the shortest $s \to t$ path before adding $c$ is different from the shortest one after. (This is the proof behind the §29.4 pitfall "just add a constant.")

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Keep each solution to ≤ 30 lines.

29.13 † Write path_weight(adj, path) that takes an adjacency list (the (neighbor, weight) form) and a list of vertices, and returns the total weight of the path, or None if any consecutive pair is not an edge. Test it on ["A", "C", "B", "D", "E"] for the road map.

29.14 Write dijkstra(adj, source) returning the dist dictionary, using heapq with lazy deletion (the stale-entry guard). Then print the distances from "A" for the road map.

29.15 † Extend your Dijkstra to dijkstra_paths(adj, source) returning (dist, prev), and write path_to(prev, target) that reconstructs the route. Print the shortest path from "A" to "E".

29.16 Write bellman_ford(vertices, edges, source) (edges are (u, v, w) triples) that returns the dist dictionary, or None if a negative cycle is reachable from the source. Test it on the two-vertex graph with edges $X \to Y:1$ and $Y \to X:-2$ and confirm it reports a negative cycle.

29.17 † Write floyd_warshall(weight) taking an $n \times n$ matrix (float('inf') for absent edges, $0$ on the diagonal) and returning the all-pairs distance matrix. Test it on the $3 \times 3$ matrix with $0 \to 1:4$, $0 \to 2:5$, $1 \to 2:-2$.

Part D — Find the error (⭐⭐)

Each argument or program below is wrong. State precisely which part fails and why, and give a fix.

29.18 † Claim: "Dijkstra works on any graph if you finalize a vertex as soon as its dist first drops below $\infty$, because that's when you've found a path to it." Find the flaw using the road map: which vertex would be finalized with the wrong distance, and what is its correct distance? Name the pitfall from §29.2.

29.19 "Proof" that Dijkstra handles negative edges: "Relaxation is safe — it never sets dist below the true distance — so whatever value a vertex is finalized with must equal its true distance. Therefore Dijkstra is correct even with negative weights. ∎" Find the flaw. (Safety gives one inequality; which other fact does correctness require, and where does the §29.3 proof actually use non-negativity?)

29.20 † A student writes Bellman-Ford but loops the passes for _ in range(len(vertices)) ($|V|$ passes) and then omits the separate detector pass, instead claiming "if the last pass changed nothing, there's no negative cycle, and if it did change something, there is one." Find the flaw. Is $|V|$ passes wrong? Is the negative-cycle conclusion drawn from "the last pass changed something" correct? Explain both.

29.21 A buggy Floyd-Warshall puts the loops in the order for i / for j / for k (source outermost, waypoint innermost). On the matrix W = [[0, INF, 1], [INF, 0, INF], [INF, 2, 0]] (edges $0\to2:1$, $2\to1:2$), the correct $D[0][1]$ is $3$ (via $0 \to 2 \to 1$). Hand-trace the buggy loop order and show it can miss this. State the correct loop order and the §29.5 mantra.

Part E — Model it (⭐⭐⭐)

29.22 † (Model it.) A budget traveler wants the cheapest itinerary from city S to city T. The available flights and fares are: S→A \$120, S→B \$200, A→B \$60, A→T \$300, B→T \$150, A→C \$90, C→T \$140. Model this as a weighted directed graph (give $V$, $E$, and $w$), state precisely which shortest-path problem you are solving (SSSP or APSP, which source), and identify by hand the cheapest fare from S to T and the route.

29.23 (Model it.) A reliability engineer wants the most reliable path through a network where each link $i$ independently succeeds with probability $p_i \in (0, 1]$, and a path's reliability is the product of its link probabilities. Shortest-path algorithms add weights; reliability multiplies them. Describe a weight transformation $w(e) = f(p_e)$ that converts "maximize the product of $p$" into "minimize the sum of $w$," so Dijkstra applies. Verify your weights are non-negative, and explain why that justifies using Dijkstra rather than Bellman-Ford.

29.24 (Model it.) In a currency-exchange market, an edge $u \to v$ has rate $r_{uv} > 0$ (one unit of currency $u$ buys $r_{uv}$ units of $v$). An arbitrage opportunity is a cycle whose rates multiply to more than $1$. Show that taking $w(u, v) = -\log r_{uv}$ turns "a cycle with product of rates $> 1$" into "a cycle of negative total weight," so detecting arbitrage becomes detecting a negative cycle. Which algorithm from this chapter detects it, and which of its passes does the work?

Part F — Conjecture and test (⭐⭐⭐)

29.25 † (Conjecture and test, then prove or disprove.) A classmate conjectures: "In a directed graph with positive weights, the shortest path between two vertices is always unique." Use code (build two or three small graphs and run your dijkstra_paths, or reason by hand) to test it. Then either prove it or produce the smallest counterexample. (Hint: what if two different paths tie in total weight?)

29.26 (Conjecture and test, then prove or disprove.) Conjecture: "If you run Dijkstra and then double every edge weight and run it again, every shortest-path distance doubles and the shortest-path tree is unchanged." Test it on the road map (compute the doubled-weight distances), then prove the general claim or find a counterexample. (Think about what scaling all weights by a constant $c > 0$ does to the weight of every path.)

29.27 † (Conjecture and test.) Conjecture: "Running Bellman-Ford for only $\lceil |V|/2 \rceil$ passes still gives correct distances on any graph with no negative cycle." Construct a graph where the unique shortest path to some vertex uses $|V| - 1$ edges (a long chain), run the truncated Bellman-Ford by hand for a few passes, and report whether the conjecture holds. What does this tell you about why the $|V| - 1$ count is tight?

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

29.28 † (Ch. 28 + 29.) BFS finds fewest-edge paths; Dijkstra finds least-weight paths. Give a single weighted graph on which the fewest-edge path from $s$ to $t$ and the least-weight path are different paths, and state both. Then explain in one sentence why BFS is exactly Dijkstra restricted to the case where the answers always coincide.

29.29 (Ch. 27 + 29.) The road map is a directed weighted graph. (a) State the handshaking lemma for an undirected graph and explain why it does not directly apply here. (b) For the road map, compute the out-degree and in-degree of every vertex, and verify that $\sum_v \deg^{+}(v) = \sum_v \deg^{-}(v) = |E|$.

29.30 (Ch. 14 + 29.) Using Big-O reasoning, compare the cost of computing all-pairs shortest paths two ways on a graph with $V$ vertices and $E$ edges: (i) Floyd-Warshall, and (ii) running Dijkstra from every vertex. For each of a dense graph ($E \approx V^2$) and a sparse graph ($E \approx V$), say which is asymptotically faster and why.

29.31 (Ch. 6 + 29.) The Dijkstra correctness proof (§29.3) is built on a loop invariant (a Chapter 6 idea). State the invariant precisely, and explain which part of the proof plays the role of "maintenance" and which uses the minimum-distance extract step. (You are mapping a graph-algorithm proof onto the induction template.)

29.32 (Deep Dive.) Prove the path-relaxation property in full (not just the scaffolded step of 29.9): by induction on $k$, after $k$ passes of relaxing all edges, $\text{dist}[v] = \delta(s, v)$ for every $v$ with a shortest path of $\le k$ edges. Then deduce Bellman-Ford's correctness for graphs with no negative cycle.

29.33 (Deep Dive — A*.) §29.6 says A* is Dijkstra with priority key $\text{dist}[v] + h(v)$, where $h$ is an admissible heuristic (never overestimates the true remaining distance to the goal $t$, i.e. $h(v) \le \delta(v, t)$). Argue informally why admissibility is exactly what is needed for A* to still return a true shortest path. (Connect to the role non-negativity played in §29.3: which inequality in the correctness argument does admissibility rescue?)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated claim, correct use of the safety-of-relaxation and optimal- substructure facts, and explicit identification of where (if anywhere) non-negativity is used.