Day 64 — Shortest paths

Day 64 — Shortest paths

Stage VI · concept day
Goal: Define weighted shortest paths; run Dijkstra by hand; understand why nonnegativity is necessary (counterexample); Bellman-Ford awareness; triangle inequality of distance; Dijkstra invariant proof sketch.

Why this matters

Routing, map navigation, network latency, and many planning problems are shortest path problems. BFS solves the unweighted (hop) case (Day 62). Dijkstra handles nonnegative weights; Bellman-Ford allows negative edges (no negative cycles). Knowing when each applies is as important as the mechanics.

Theory

Weighted graphs

Each edge \(e\) has a real weight \(w(e)\) (cost, length, time).
Weight of a path = sum of its edge weights.
Shortest path \(s\)–\(t\): path of minimum weight (if one exists).
Distance \(\delta(s,t)\) = that minimum weight, or \(+\infty\) if unreachable, or \(-\infty\) if arbitrary negative looping (negative cycle reachable).

Triangle inequality for distances

If \(\delta\) is finite (no negative cycles),

\[ \delta(s,t)\le \delta(s,u)+\delta(u,t). \]

Also \(\delta(s,t)\le \delta(s,u)+w(u,t)\) for any edge \(u\to t\) (edge relaxation idea).

Relaxation

For edge \(u\to v\):

\[ \text{if } d(v) > d(u)+w(u,v)\text{ then } d(v)\leftarrow d(u)+w(u,v),\ \mathrm{parent}(v)\leftarrow u. \]

All classical algorithms repeatedly relax edges under different schedules.

Dijkstra’s algorithm (nonnegative weights)

Assumption: \(w(e)\ge 0\) for all edges.

Idea: grow the set \(S\) of vertices whose final distance from \(s\) is known; always add the unsettled vertex \(u\) with smallest tentative \(d(u)\); relax edges out of \(u\).

Hand-level steps:

1. \(d(s)=0\), \(d(v)=\infty\) for \(v\neq s\); \(S=\emptyset\).
   
2. While \(S\neq V\) (or unsettled remain reachable): pick \(u\notin S\) with minimal \(d(u)\); add \(u\) to \(S\); relax all edges from \(u\).
   
3. Stop when \(t\in S\) if only \(s\)–\(t\) needed.

Data structure culture: heap → \(O(m+n\log n)\) variants; today arrays OK for tiny \(n\).

Dijkstra invariant (proof sketch)

Claim. When \(u\) is added to \(S\), \(d(u)=\delta(s,u)\).

Sketch. Induct on \(|S|\). When picking \(u\), suppose for contradiction \(d(u)>\delta(s,u)\). Consider a true shortest path \(P\) to \(u\); let \(xy\) be the first edge on \(P\) with \(x\in S\), \(y\notin S\) (exists). Then \(d(y)=\delta(s,y)\) by IH on \(x\) and relaxation, and \(\delta(s,y)\le\delta(s,u)<d(u)\), and nonnegativity ⇒ \(\delta(s,y)\le\delta(s,u)\), so \(y\) would have smaller tentative key than \(u\)—contradiction to choice of \(u\). \(\square\)

Nonnegativity used so prefix of shortest path is shortest and costs don’t decrease later.

Why negatives break Dijkstra (counterexample)

Vertices \(s,a,t\). Edges \(s\to a\) weight \(1\), \(s\to t\) weight \(2\), \(a\to t\) weight \(-100\) (or undirected careful).
More classic: \(s\to a\) weight 2, \(s\to b\) weight 5, \(b\to a\) weight \(-10\) directed…
Simple directed:

• \(s\to a\) weight 1
  
• \(s\to t\) weight 100
  
• \(a\to b\) weight 1
  
• \(b\to t\) weight 1
  
• and a negative edge that should update after \(t\) settled wrongly

Standard counterexample:

Vertices \(s,u,v\). Edges: \(s\to u\) weight 1, \(s\to v\) weight 100, \(u\to v\) weight \(-50\) wait still may work sometimes.

Classic:

\(s\to a:5\), \(s\to b:1\), \(b\to a:-2\) (directed). Dijkstra may finalize \(a\) with 5 before using \(b\to a\) giving \(1+(-2)=-1\). When \(b\) is processed first (\(d=1\)), relax \(a\) to \(-1\)—actually OK if \(a\) not yet finalized.

Better known failure: after finalizing a node, a negative edge into it from a later node would need update—Dijkstra never reopens. Example:

• \(s\to a:1\), \(s\to b:100\), \(a\to b:1\), \(b\to c:-100\), and path using \(c\) back…

Use this standard:

Graph: \(s\to a\) weight 2; \(s\to b\) weight 3; \(b\to a\) weight \(-2\); target distances \(\delta(s,a)=1\) via \(s{-}b{-}a\). If Dijkstra picks \(a\) first among \(\{a,b\}\) with tentative 2 (before processing \(b\)’s negative), it finalizes \(a\) at 2 wrongly.

Trace: init \(d(s)=0,d(a)=d(b)=\infty\). Relax from \(s\): \(d(a)=2,d(b)=3\). Pick \(a\) (smaller), finalize \(d(a)=2\). Pick \(b\), relax \(b\to a\) to \(3-2=1\) but \(a\) already finalized—Dijkstra doesn’t update ⇒ wrong.

Bellman-Ford (awareness)

Allow negative edge weights; detect negative cycles.

• Relax all edges \(|V|-1\) times.
  
• One more pass: if any relaxation succeeds, a negative cycle is reachable from \(s\).
  
• Time \(O(|V||E|)\); simpler invariant, slower.

Floyd-Warshall (awareness)

All-pairs; \(O(n^3)\); allows negatives, detects neg cycles on diagonal.

BFS special case

All weights 1 (or equal positive): BFS ≡ Dijkstra with deque optimizations (0-1 BFS culture).

DAG shortest paths

Topo order + one relax per edge: \(O(n+m)\), allows negative edges (no cycles at all).

Worked examples

Example 1 — Dijkstra hand

Vertices \(S,A,B,C,T\).
Weights: \(SA=2,SB=5,AB=1,AC=4,BC=1,BT=3,CT=1\).

Step	Pick	\(d(S,A,B,C,T)\)	notes
init		0,∞,∞,∞,∞
relax S	S	0,2,5,∞,∞
pick A	A	0,2,3,6,∞	AB→3, AC→6
pick B	B	0,2,3,4,6	BC→4, BT→6
pick C	C	0,2,3,4,5	CT→5
pick T	T	0,2,3,4,5	done

Path \(S{-}A{-}B{-}C{-}T\) weight 5 (or check \(SABT=2+1+3=6\) worse).

Example 2 — Reconstruct

Parents: \(A\leftarrow S\), \(B\leftarrow A\), \(C\leftarrow B\), \(T\leftarrow C\) ⇒ path \(S,A,B,C,T\).

Example 3 — Negative counterexample

As above: \(s\to a:2\), \(s\to b:3\), \(b\to a:-2\). Dijkstra can finalize \(a\) at 2; true \(\delta(s,a)=1\).

Example 4 — Unreachable

Isolated \(X\): \(d(X)=\infty\) always.

Example 5 — Zero weights

Zero-weight edges OK for Dijkstra; negatives not.

Example 6 — Triangle

After algorithm, check \(d(t)\le d(u)+w(u,t)\) for all edges (local optimality).

Example 7 — BFS comparison

All weights 1 on G1 Day 62: Dijkstra distances = BFS dist.

Example 8 — DAG DP

Edges only forward in topo; relax in topo order once.

Example 9 — Multiple shortest

Equal weights may give multiple parent choices—any OK.

Example 10 — Bellman-Ford one neg

Same counterexample graph: BF finds \(d(a)=1\).

Example 11 — Negative cycle

\(a\to b:1\), \(b\to a:-2\): BF detects; distances not well-defined for nodes on cycle.

Example 12 — Prim vs Dijkstra

Similar “grow set by min key” structure; different objective (MST vs paths)—don’t confuse.

Example 13 — Bidirectional Dijkstra awareness

Meet-in-middle for \(s\)–\(t\) in practice—optional.

Example 14 — Potentials / A*

Heuristic estimates—awareness for maps.

Example 15 — Full trace discipline

Never pick a vertex twice in classical Dijkstra; keep a table each iteration.

Exercises

1. Define path weight and \(\delta(s,t)\).
   
2. Run Dijkstra on Example 1 from scratch; report \(d(T)\) and path.
   
3. Change \(CT\) to 10; recompute \(d(T)\).
   
4. Prove triangle inequality for \(\delta\) when no neg cycles.
   
5. Explain the negative counterexample carefully with a step table.
   
6. Why nonnegativity is used in the invariant sketch.
   
7. All weights equal to 5: relate to BFS.
   
8. Bellman-Ford: how many full relax passes for \(n\) vertices?
   
9. Detect negative cycle: what extra pass does.
   
10. DAG: give a 4-vertex example and compute shortest from source by topo.
    
11. True/false: Dijkstra works with negative edges if no negative cycle.
    
12. CS: OS routing / OSPF culture uses Dijkstra.
    
13. Hand Dijkstra on a graph with a zero-weight edge.
    
14. Show two different shortest paths same weight.
    
15. Floyd-Warshall: what does \(D[i][i]<0\) mean?
    
16. Compare complexity culture Dijkstra vs BF.
    
17. If \(t\) finalized, can we stop early? Yes for classical Dijkstra.
    
18. Undirected graphs: treat as bidirectional arcs with same weight; negatives problematic (edge both ways).
    
19. Challenge: proof fill-in of Dijkstra invariant details.
    
20. Build a graph where BFS hops path ≠ min weight path.
    
21. Parent pointers form a shortest path tree—define.
    
22. What if decrease-key missed in implementation—wrong answers.
    
23. Exercise: \(d\) values after each pick for a 6-vertex complete graph with given weights (you invent).
    
24. Critical path is longest not shortest—contrast Day 63.
    
25. Portfolio: one Dijkstra table + one written invariant paragraph.

CS connection

• Network routing (link-state / Dijkstra).
  
• Maps and navigation.
  
• Game AI pathfinding (A* variant).
  
• Currency arbitrage as negative cycles (BF).
  
• Difference constraints systems via BF (awareness).

Common pitfalls

Pitfall	What to do instead
Dijkstra + negatives	Use BF or cancel
Confusing MST Prim with Dijkstra	Different keys/goals
Forgetting to update parent	Need for path reconstruct
Stopping with wrong early exit	Only safe when \(t\) extracted
Undirected negative edges	Model carefully

Checkpoint

• Dijkstra hand table competent
  
• Nonnegativity counterexample
  
• Invariant statement
  
• Bellman-Ford role
  
• Triangle inequality
  
• Exercises 1–15
  
• Path reconstruction

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

2. \(d(T)=5\); path \(SABCT\).
   
3. Then \(SABT=6\) may win if CT=10: \(d(T)=6\) via \(BT\).
   
4. Divide all by 5 ≡ hop count.
   
5. \(n-1\) passes.
   
6. False in general.
   
7. Negative cycle.

Deepening notes

Dijkstra table template

iter	pick \(u\)	\(d(\cdot)\) vector	parent updates
0	—
1	\(s\)

Never extract a vertex twice in the classical version.

Negative counterexample (canonical writeup)

Arcs: \(s\to a\) weight 2, \(s\to b\) weight 3, \(b\to a\) weight \(-2\).
Tentative after \(s\): \(d(a)=2,d(b)=3\). Extract \(a\) with 2. Later \(b\) would give \(d(a)=1\) but \(a\) finalized—wrong. True \(\delta(s,a)=1\).

BF vs Dijkstra chooser

Situation	Use
All \(w\ge 0\)	Dijkstra
Some \(w<0\), no neg cycle needed detect	BF
Neg cycle detect	BF extra pass
DAG	topo one-pass
Unweighted	BFS

Extra drills

D1. Dijkstra recompute Day 64 Ex.1 changing \(SB=1\).
D2. Show triangle inequality fail if neg cycle.
D3. BF on the counterexample—final \(d(a)\).
D4. DAG shortest with a negative edge.
D5. Two shortest paths same weight—list both.
D6. Zero-weight edges only: relate to BFS.
D7. Early exit when \(t\) extracted—justify.
D8. Write invariant paragraph from memory.

Flash

relax \(d(v)>d(u)+w(u,v)\); Dijkstra needs \(w\ge 0\); BF \(O(nm)\); \(\delta(s,t)\le\delta(s,u)+\delta(u,t)\).

Exam drill block

E1. Dijkstra on triangle \(s,a,t\) with \(w(sa)=5,w(st)=10,w(at)=3\)—final \(d(t)\) and path.
E2. Same with \(w(at)=-1\)—why Dijkstra fails if it finalizes \(a\) early (or if negatives allowed).
E3. State Dijkstra’s invariant: extracted vertices have \(d(u)=\delta(s,u)\).
E4. Bellman-Ford: how many relax-all-edges passes on \(n\) vertices? Extra pass for?
E5. Triangle inequality for shortest-path distances (no neg cycle).
E6. DAG shortest: one topo pass of relaxations.
E7. Unweighted ⇒ BFS special case of unit weights.
E8. Reconstruct path from parent array; handle unreachable.
E9. True/false: (i) Dijkstra OK with negative edges if no neg cycle (ii) BF detects neg cycle (iii) \(\delta\) always finite.
E10. Early exit when target extracted—when valid?

Mini solutions

E1. Path \(s{-}a{-}t\) weight \(8\).
E4. \(n-1\) passes; \(n\)th pass detects negative cycle if still improving.
E9. F (counterexamples exist); T; F (unreachable \(\infty\)).
E10. When only \(d(t)\) needed and nonnegative weights—yes after extract \(t\).

Algorithm chooser (reprise)

Case	Algorithm
Unweighted	BFS
Nonnegative weights	Dijkstra
Negatives, no need for fancy heap	Bellman-Ford
DAG	Topo DP
All-pairs dense	Floyd-Warshall awareness

Synthesis

Relaxation is the atomic update. Dijkstra greedily finalizes the closest unsettled vertex—correct iff weights nonnegative. Bellman-Ford repeats global relaxations and can detect negative cycles. Triangle inequality holds for true distances \(\delta\). Always reconstruct paths via parents and report unreachable vertices.

S1. Full Dijkstra table on a 6-vertex weighted graph.
S2. Run BF on a digraph with a negative edge but no neg cycle.
S3. Cold: write the negative counterexample that breaks Dijkstra; one-sentence invariant.

Tomorrow

Day 65 — Bipartite graphs & matchings: 2-coloring; odd cycles; Hall’s theorem; König awareness.