Day 22 — BFS/DFS, DAGs & Shortest Paths

Updated

July 30, 2025

Day 22 — BFS/DFS, DAGs & Shortest Paths

Day 62 — BFS & DFS

Stage VI · concept day
Goal: Hand-simulate BFS and DFS on small graphs; understand BFS levels and unweighted shortest paths; DFS discovery/finish times; edge type awareness (tree/back/forward/cross)—tables, not code labs.

Why this matters

BFS and DFS are the two foundational graph traversals. Shortest paths in unweighted graphs, connectivity, cycle detection, topological sort (Day 63), and many compilers/networks algorithms are BFS/DFS wrappers. Hand simulation builds the mental model that coding without understanding lacks.

Theory

Graph exploration

From a start vertex \(s\), traverse means visit vertices (and edges) in a systematic order until a component (or reachable set) is exhausted.
Maintain visited marks so each vertex is processed once (in the basic versions).

Breadth-first search (BFS)

Idea: explore in layers of increasing distance from \(s\).

Queue discipline: FIFO.

High-level:

  1. Set \(\mathrm{dist}(s)=0\), parent\((s)=\mathrm{null}\); enqueue \(s\); mark visited.
  2. While queue nonempty: dequeue \(u\); for each neighbor \(v\) (in agreed order): if not visited, set parent\((v)=u\), \(\mathrm{dist}(v)=\mathrm{dist}(u)+1\), mark visited, enqueue \(v\).

BFS tree: edges \(\{u,v\}\) where parent\((v)=u\).
Levels: vertices with equal \(\mathrm{dist}\).

BFS and shortest paths (unweighted)

Theorem. In an unweighted undirected (or unweighted directed) graph, when BFS from \(s\) finishes, \(\mathrm{dist}(v)\) equals the length of a shortest \(s\)–\(v\) path (∞ if unreachable). Parent pointers reconstruct a shortest path.

Why (invariant sketch). Vertices are first found in nondecreasing distance order; when \(v\) is first reached from \(u\), all shorter paths would have found \(v\) earlier—standard queue invariant.

Does not work with general positive weights—need Dijkstra (Day 64).

Depth-first search (DFS)

Idea: go deep along a path; backtrack when stuck.

Stack discipline: LIFO (recursion stack).

Timestamps: \(\mathrm{disc}(v)\) when first seen; \(\mathrm{fin}(v)\) when adjacency fully processed.

High-level recursive:

time ← 0
DFS-visit(u):
  time ← time+1; disc(u) ← time; color u gray
  for each neighbor v (fixed order):
    if v white: parent(v)←u; DFS-visit(v)
  time ← time+1; fin(u) ← time; color u black

Forest: restart on unvisited vertices for full graph DFS.

Edge types in DFS (directed graphs)—awareness

During DFS on a digraph, classify edge \(u\to v\):

Type When
Tree \(v\) first discovered from \(u\)
Back \(v\) is ancestor of \(u\) (gray) — cycle indicator
Forward \(v\) is descendant, already finished, not tree edge
Cross all other (to other branch / finished non-descendant)

Undirected: only tree and back edges (forward/cross coincide with back in undirected classification).
Cycle detection undirected: back edge to visited non-parent.
Cycle detection directed: back edge to gray vertex.

Parenthesis theorem (lite)

Discovery/finish intervals nest or are disjoint—like matched parentheses. Descendants have intervals inside ancestors.

Neighbor order

Always specify: alphabetical, numerical, given adjacency list order. Different orders ⇒ different trees/forests, same distances for BFS.

Complexity culture

Adjacency list: \(O(|V|+|E|)\) time for BFS or DFS.

Worked examples

Graph G1 (running):
Vertices \(S,A,B,C,T\).
Edges undirected: \(S{-}A,S{-}B,A{-}B,A{-}C,B{-}C,B{-}T,C{-}T\).
Neighbor order: alphabetical.

Example 1 — BFS from \(S\)

Queue trace:

Step Dequeue Enqueue dist updates
0 — \(S\) \(d(S)=0\)
1 \(S\) \(A,B\) \(d(A)=d(B)=1\)
2 \(A\) \(C\) \(d(C)=2\)
3 \(B\) \(T\) \(d(T)=2\)
4 \(C\) —
5 \(T\) —

Parents: \(A\leftarrow S\), \(B\leftarrow S\), \(C\leftarrow A\), \(T\leftarrow B\) (if \(B\) before \(C\) processes \(T\)—when \(B\) dequeued, \(C\) already visited from \(A\), so \(T\) from \(B\)).
Discovery order: \(S,A,B,C,T\).
Shortest \(S\)–\(T\): length 2, e.g. \(S{-}B{-}T\).

Example 2 — DFS from \(S\) (alphabetical)

\(S\) disc=1; visit \(A\) disc=2; from \(A\) visit \(B\) disc=3; from \(B\) visit \(C\) disc=4; from \(C\) visit \(T\) disc=5; \(T\) fin=6; \(C\) fin=7; \(B\) fin=8; \(A\) fin=9; \(S\) fin=10.
(Exact numbers depend on when neighbors already visited—work carefully on paper.)

Example 3 — BFS distances as levels

Level 0: \(\{S\}\); level 1: \(\{A,B\}\); level 2: \(\{C,T\}\).

Example 4 — Unreachable

Add isolated \(X\): BFS from \(S\) never visits \(X\); need multi-source or restart for full cover.

Example 5 — Directed DFS edge types

Arcs: \(1\to2,2\to3,3\to1,1\to4\).
DFS from 1: tree edges \(1\to2\to3\); \(3\to1\) back; \(1\to4\) tree. Cycle detected via back edge.

Example 6 — Undirected cycle

\(C_3\): DFS finds back edge to ancestor.

Example 7 — BFS not for weights

Edges weights 1 on long path and 100 on short edge—BFS by hops ≠ min weight.

Example 8 — Path reconstruction

Follow parents from \(T\) to \(S\): \(T\leftarrow B\leftarrow S\).

Example 9 — DFS forest

Two components: two DFS trees in the forest.

Example 10 — Finish order

In a DAG, reverse finish order is a topological order (Day 63).

Example 11 — Hand table template

Vertex parent dist / disc fin color timeline

Fill while simulating—do not skip.

Example 12 — Same BFS distances, different trees

Neighbor order \(S\): \(B\) before \(A\) ⇒ parents swap for some nodes; distances unchanged.

Example 13 — Bipartite test via BFS

Color levels alternating; odd cycle ⇒ conflict (Day 65).

Example 14 — Layer counts

Number of vertices at dist \(k\) from \(s\) in a tree equals size of level \(k\).

Example 15 — Call stack depth

DFS depth can be \(\Theta(n)\) on a path—recursion limits culture in implementation (awareness).

Exercises

  1. Run BFS on G1 from \(A\); report dist and parents (alpha neighbors).
  2. Run DFS on G1 from \(A\); report disc/fin (approximate carefully).
  3. Prove: BFS finds shortest hop paths (write invariant in your words).
  4. Draw BFS tree and DFS tree of G1 from \(S\).
  5. Directed: vertices \(1,2,3\), arcs \(1\to2,1\to3,2\to3\). DFS from 1: classify \(2\to3\).
  6. Detect cycle in undirected G1 via DFS—where is back edge?
  7. Graph \(P_5\): BFS from end vs middle—distances.
  8. When is BFS tree a path?
  9. Multi-source BFS idea (super-source)—one sentence.
  10. Complete BFS table for \(K_4\) from one vertex.
  11. CS: web crawler closer to BFS or DFS?
  12. Why adjacency matrix BFS is \(O(n^2)\) typically.
  13. Give a graph where DFS tree depth ≫ BFS tree depth.
  14. Parenthesis: check intervals nest for a DFS you ran.
  15. Hand-sim Kruskal? (wrong day)—instead: hand-sim BFS levels for star \(K_{1,5}\).
  16. Digraph with a cross edge: invent 4 vertices.
  17. Reconstruct path \(S\) to \(T\) in Example 1.
  18. True/false: DFS always finds shortest paths.
  19. Connected components via multi-start BFS.
  20. Color-coding visualization of gray/black in DFS.
  21. Challenge: diameter via multi BFS twice on trees.
  22. Edge classification undirected: only tree/back—explain.
  23. G1: is dist\((S,T)=2\) unique path?
  24. Write pseudocode BFS and DFS from memory.
  25. Portfolio: full tables for BFS+DFS on a 6-vertex graph of your design.

CS connection

  • Shortest routes unweighted (hops in networks).
  • Garbage collectors / crawlers.
  • Cycle detection in undirected/directed graphs.
  • Topological sort via DFS finish times.
  • Bipartite check, connected components, SCC algorithms (Kosaraju/Tarjan culture).

Common pitfalls

Pitfall What to do instead
Forgetting visited mark Mark when enqueued (BFS) / discovered (DFS)
BFS for weighted graphs Dijkstra/Bellman-Ford
Ambiguous neighbor order Fix order before sim
DFS “shortest” claim False in general
Mixing disc and fin Two timestamps

Checkpoint

  • BFS queue sim with dist/parent table
  • DFS disc/fin table
  • Shortest unweighted theorem statement
  • Edge types awareness (directed)
  • Cycle detection rules
  • Exercises 1–15
  • G1 both algorithms cold

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. Invariant: queue holds vertices of at most two consecutive distances; first time reached is minimal hops.
  2. When the graph is a path starting at an endpoint (BFS tree unique path).
  3. Often BFS (politeness layers) or priority—varies.
  4. False.
  5. No—\(S{-}A{-}C{-}T\) length 3; \(S{-}B{-}T\) and \(S{-}A{-}B{-}T\) etc.; two hop: \(SBT\), and \(S{-}?\) \(S{-}A{-}C{-}T\) is 3; is \(S{-}B{-}C{-}T\) 3; two-hop paths: \(SBT\) only? Also no \(S{-}A{-}T\) edge. So unique length-2 path \(S{-}B{-}T\) if \(C\) not adjacent \(S\). Yes unique.

Deepening notes

BFS invariant (one more time)

At all times, the queue contains vertices of distance \(k\) and/or \(k+1\) only for some \(k\), and all vertices of distance \(<k\) are settled. First discovery is shortest.

DFS timestamp example table skeleton

\(v\) disc fin parent

Fill for G1 until automatic.

Edge type detection rules (directed)

  • Tree: discover white
  • Back: to gray
  • Forward/cross: to black (distinguish by interval nest)

Extra drills

D1. BFS from \(T\) on G1.
D2. DFS from \(B\) on G1.
D3. Bipartite test via BFS coloring on G1 (will fail).
D4. Components via multi-source BFS on a disconnected graph.
D5. Directed cycle via gray back edge invent.
D6. Reconstruct three paths using parents.
D7. Compare BFS trees under two neighbor orders.
D8. Diameter of a tree via double BFS method outline.

Flash

BFS queue FIFO → hops; DFS stack LIFO → disc/fin; undirected edges tree/back; \(O(n+m)\) list.

Exam drill block

E1. BFS from a leaf of a path \(P_6\): write dist and parent arrays.
E2. BFS on \(K_{1,4}\) from the center; from a leaf.
E3. Prove: first time BFS reaches \(v\), \(d(v)=\delta(s,v)\) (unweighted).
E4. DFS disc/fin on a rooted binary tree shape (root + two children + one grandchild).
E5. Classify undirected edges as tree/back on a unicyclic graph.
E6. Directed: invent a back edge to gray; state cycle.
E7. Reconstruct shortest path \(s\) to \(t\) from parent pointers.
E8. Multi-source BFS: all vertices distance to nearest hospital (idea).
E9. True/false: (i) DFS always finds shortest hops (ii) BFS tree depends on neighbor order (iii) \(O(n+m)\) with adj lists.
E10. Diameter of a tree via two BFS runs (method outline).

Mini solutions

E1. Distances \(0,1,2,3,4,5\) along the path.
E2. From center all leaves dist 1; from leaf: center 1, other leaves 2.
E9. F; T; T.
E10. BFS from arbitrary \(u\) to farthest \(x\); BFS from \(x\) to farthest \(y\); \(\mathrm{diam}=d(x,y)\).

Complexity and representation

Representation BFS/DFS time
Adj lists \(\Theta(n+m)\)
Adj matrix \(\Theta(n^2)\)

Prefer lists for sparse graphs. Queue (BFS) vs stack/recursion (DFS).

Synthesis

BFS layers = hop distances; DFS timestamps structure the recursion tree and classify edges. Unweighted shortest paths are BFS, not Dijkstra. Undirected: tree + back edges; directed: tree/back/forward/cross. Both are \(O(n+m)\) workhorses for connectivity, bipartiteness (BFS coloring), and cycle detection.

S1. Full BFS table on a 7-vertex graph with a cycle.
S2. Full DFS disc/fin table on the same graph.
S3. Cold: why FIFO ⇒ shortest hops; one sentence each for back edge meanings undirected vs directed.
S4. Bipartite test: BFS 2-color a cycle \(C_5\) (fail) and \(C_6\) (succeed).
S5. Parent-pointer path reconstruction: write the reverse-walk algorithm in three lines.

Tomorrow

Day 63 — DAGs & topological order: equivalent defs; Kahn vs DFS; longest path DP; critical path lite.

Day 63 — DAGs & topological order

Stage VI · concept day
Goal: Characterize DAGs; prove topological orders exist iff the digraph is a DAG; understand Kahn and DFS-based topo ideas; longest path in a DAG via DP; scheduling / critical path lite.

Why this matters

Build systems, package managers, spreadsheets, course prerequisites, and make/cmake dependency graphs are DAGs when well-formed—and cyclic when you have a bug. Topological order is the legal execution/install order. Longest paths in DAGs give critical paths in project scheduling—polynomial, unlike general graphs.

Theory

Directed acyclic graph

A DAG is a directed graph with no directed cycles.

Equivalent / related facts:

  1. \(G\) is a DAG.
  2. \(G\) has a topological order (see below).
  3. DFS on \(G\) produces no back edges.
  4. Strongly connected components are all single vertices (condensation of any digraph is a DAG).

Topological order

A topological ordering of a digraph is a listing \(v_1,\ldots,v_n\) of all vertices such that every arc \(v_i\to v_j\) has \(i<j\) (all edges point forward in the list).

Theorem. A finite digraph has a topological order if and only if it is a DAG.

Proof sketch.

  • \((\Rightarrow)\) If a cycle exists, vertices on the cycle cannot be ordered with all arcs forward.
  • \((\Leftarrow)\) Every finite DAG has a vertex of in-degree 0 (else walking backward forever yields a cycle). Place it first; delete it; repeat (induction). This is Kahn’s algorithm idea.

Non-uniqueness: many topos if incomparable vertices (e.g. two sources).

Kahn’s algorithm (idea)

  1. Compute in-degrees; enqueue all in-degree 0.
  2. While queue nonempty: pop \(u\), append to order; for each out-neighbor \(v\), decrement in-degree; if 0, enqueue.
  3. If output size \(<n\), a cycle exists (not a DAG).

Hand-simulate with a table of in-degrees over time.

DFS-based topological sort (idea)

Run DFS; list vertices in decreasing finish time.
On a DAG, this is a topological order.
Why: for arc \(u\to v\), \(v\) finishes before \(u\) (cannot be back edge), so \(u\) appears later in decreasing-finish listing… actually: decreasing finish puts \(u\) before \(v\) if \(u\) finishes after \(v\)—standard CLRS argument: tree/forward/cross edges consistent with topo when no back edges.

Longest path in a DAG

In general graphs, longest path is hard (related to Hamilton). In a DAG, linear-time DP:

  1. Topologically order vertices.
  2. Let \(L(v)=\) length of longest path ending at \(v\) (or starting from sources—be consistent).
  3. Process in topo order:

\[ L(v)=\max\{0\text{ or }L(u)+w(u,v):u\to v\}, \]

depending on node weights vs edge weights.

Node-weighted critical path: \(L(v)=w(v)+\max_{u\to v}L(u)\) with \(L=w\) at sources.

Scheduling / critical path lite

Tasks = vertices; precedence \(u\to v\) means \(u\) before \(v\); duration \(w(v)\).
Critical path = longest path in this DAG (minimum project time if infinite parallelism subject to precedence).
Slack = how much a task can slip without delaying project—optional awareness.

Sources and sinks

Source: in-degree 0. Sink: out-degree 0.
DAG with ≥1 vertex has ≥1 source and ≥1 sink.

Transitive closure (lite)

Reachability matrix; can be computed via DFS from each vertex or Floyd–Warshall culture—\(O(n^3)\) or better with structure.

Worked examples

Example 1 — Topo

Vertices \(A,B,C,D\); arcs \(A\to C,B\to C,C\to D,A\to D\).
Sources initially: \(A,B\). One topo: \(A,B,C,D\); also \(B,A,C,D\).
Not topo: \(A,C,B,D\) (\(B\to C\) points backward).

Example 2 — Cycle

Add \(D\to A\): no topo; Kahn stuck after processing some vertices.

Example 3 — Kahn table

Order step Queue (alpha) In-deg \(A,B,C,D\) Emit
start \(A,B\) 0,0,2,2
1 \(B\) 0,0,1,1 \(A\)
2 \(C?\) wait after \(B\): C:0,D:1 \(B\)
… \(C,D\)

Work carefully on paper.

Example 4 — DFS finish

On Example 1, DFS from \(A\) then \(B\) may finish \(D,C,A,B\)—decreasing finish: \(B,A,C,D\) or similar topo.

Example 5 — Longest path edges weight 1

Same graph unweighted hops: longest path length 2 (\(A\to C\to D\) or \(B\to C\to D\)).

Example 6 — Task durations

Tasks \(A(2),B(3),C(4),D(1)\); arcs as Ex. 1.
\(L(A)=2,L(B)=3\), \(L(C)=4+\max(L(A),L(B))=4+3=7\), \(L(D)=1+\max(L(C),L(A))=1+7=8\).
Project time 8; critical path \(B{-}C{-}D\).

Example 7 — Package install

Packages with dependencies form DAG if no circular depends; topo = valid install order.

Example 8 — Spreadsheet

Cell formulas referencing others: evaluation order = topo; circular ref = cycle.

Example 9 — Single vertex

DAG; topo: that vertex only.

Example 10 — Empty arcs

Any order is topological.

Example 11 — Unique topo

Hamiltonian path that includes all as only linear extension—e.g. a single directed path graph has unique topo.

Example 12 — Condensation

Any digraph’s SCCs contracted → DAG of components; topo of condensation = order of processing components.

Example 13 — Detect cycle via Kahn

If queue empties early, remaining vertices all have positive in-degree → cycle among them.

Example 14 — Longest path DP table

Process \(A,B,C,D\): fill \(L\) as Ex. 6.

Example 15 — Why general longest path hard

If you could longest-path in general graphs efficiently, you could detect Hamilton paths—NP-hard culture (Day 66).

Exercises

  1. Define DAG and topological order.
  2. Prove: cycle ⇒ no topo.
  3. Prove: finite DAG ⇒ vertex of in-degree 0.
  4. Find all topological orders of Ex. 1.
  5. Kahn full trace on Ex. 1.
  6. Add one arc to create a cycle; show Kahn fails.
  7. DFS finish method on a 5-vertex DAG you draw.
  8. Longest path (hop count) in a tournament that is a DAG (transitive).
  9. Critical path with node weights on a 5-task chain.
  10. Course prereqs: CS1→CS2→OS, CS1→DS→OS: topos and critical if equal duration.
  11. True/false: unique topo ⇔ underlying structure is a Hamiltonian path of forced order.
  12. CS: make dependency DAG.
  13. Number of topos of \(n\) isolated vertices: \(n!\).
  14. Number of topos of a directed path of \(n\): 1.
  15. Condensation of a digraph with one 2-cycle and one extra vertex.
  16. Prove sinks exist in finite DAGs.
  17. Edge \(u\to v\) with both in-degree 0? Impossible unless… no, \(v\) would have in-degree ≥1.
  18. Schedule with parallel processors lite: critical path still lower bound.
  19. Implement? No—hand DP only.
  20. Find longest path in DAG with negative edge weights (still OK if no cycle).
  21. Challenge: count topological orders of a small poset (Day 40 link).
  22. Why DFS back edge ⇔ cycle (directed).
  23. Give two nonisomorphic DAGs on 4 verts with different # topos.
  24. Package: A needs B,C; B needs D; C needs D—list topos.
  25. Write a 1-page cheat sheet: Kahn + DP longest path.

CS connection

  • Build systems, package managers, module loaders.
  • Instruction scheduling / compiler dependency DAGs.
  • Data pipelines / Airflow-style task graphs.
  • Critical path method (CPM) in project management.
  • Typeclass / trait resolution order culture.

Common pitfalls

Pitfall What to do instead
Topo on undirected graphs Need orientation / digraph
Assuming unique topo Many DAGs have many
Longest path algorithms on cyclic graphs NP-hard; only DAG DP
Kahn without cycle check Compare output length to \(n\)
Confusing in-degree 0 with source after deletes Dynamic in-degrees

Checkpoint

  • DAG ⇔ has topo order
  • Kahn hand simulation
  • DFS finish idea
  • Longest path DP on DAG
  • Critical path one example
  • Exercises 1–15
  • Cycle detection via Kahn / back edge

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. If all in-degree ≥1, follow incoming arcs backward; finite ⇒ cycle.
  2. \(A,B,C,D\) and \(B,A,C,D\) only (C before D; A,B before C).
  3. Essentially yes for the partial order being a total order.
  4. \(n!\).
  6. \(D\) first; then \(B,C\) any order; then \(A\): two topos \(D,B,C,A\) and \(D,C,B,A\).

Deepening notes

Why every finite DAG has a source

If every vertex has in-degree ≥1, start anywhere and walk backward along incoming arcs; finite vertex set ⇒ repeat ⇒ directed cycle. Contradiction.

Kahn correctness sketch

Each emitted vertex had in-degree 0 in the residual graph, so all its predecessors already emitted—hence all arcs point forward in the output. If not all emitted, residual has min in-degree ≥1 ⇒ cycle.

Critical path formulas

Node weights \(w(v)\):
\(L(v)=w(v)+\max_{u\to v}L(u)\) (sources: \(L=w\)).
Project duration \(\max_v L(v)\).
Edge-weighted longest path analogous with \(L(v)=\max_{u\to v}(L(u)+w(u,v))\).

Extra drills

D1. All topos of a small V-shaped DAG.
D2. Kahn fail on a 3-cycle.
D3. DFS finish topo on 5-vertex DAG.
D4. Critical path 6 tasks.
D5. Condensation of two SCCs with arcs between.
D6. Unique topo characterization.
D7. Longest hop path in a grid DAG (only right/up).
D8. Package diamond dependency topos count.

Flash

DAG ⇔ has topo; Kahn = peel in-degree 0; longest path DP in topo order; critical path = longest path.

Exam drill block

E1. Prove finite DAG has a source.
E2. All topological orders of a diamond DAG (A→C, B→C, A→D, B→D, C→E, D→E)—list.
E3. Kahn full table on that diamond.
E4. Detect cycle with Kahn when D→A added.
E5. Node-weighted critical path: invent 6 tasks.
E6. DFS finish topo on a path digraph.
E7. Why longest path on general graphs is hard (one sentence).
E8. Condensation of a digraph with one 2-cycle.
E9. Number of topos of empty digraph on 4 verts.
E10. Package: A needs B,C; B needs D; C needs D; E needs A—topos count.

Mini solutions

E2. Orders with \(\{A,B\}\) before \(\{C,D\}\) before \(E\), and \(A,B\) free, \(C,D\) free subject to their arcs—careful enumeration.
E9. \(4!=24\).
E10. \(D\) first; \(B,C\) free; \(A\); \(E\) last: 2 topos.

Topological order cheat sheet

Method Idea Detects cycles?
Kahn Peel in-degree 0; emit; reduce successors Yes—if leftover vertices
DFS finish Emit on finish time reverse order Yes—back edge to gray

Equivalent for finite digraphs: acyclic ⇔ has a topological order ⇔ every walk is a path (no return) ⇔ DFS has no back edges.

Longest path DP (node weights)

Process vertices in topo order.
\(L(v)=w(v)+\max_{u\to v} L(u)\) (sources: \(L(v)=w(v)\)).
Project length \(=\max_v L(v)\). Edge weights: \(L(v)=\max_{u\to v}(L(u)+w(u,v))\).
Why DAG only: general longest path is NP-hard; topo order makes DP valid.

Condensation

Contract each SCC to a supernode: the condensation is always a DAG. Edges between SCCs induce a partial order on components—build/deploy “layers.”

Synthesis

DAGs model dependencies without circular waits. Topological order linearizes prerequisites (Kahn or DFS). Longest/shortest paths become one-pass DP in topo order—critical path analysis. Condensation reduces general digraphs to DAG-of-SCCs.

S1. Kahn full trace on a 6-task dependency digraph.
S2. Critical path with invented node weights on that digraph.
S3. Cold: prove finite DAG has a source; unique topo ⇔ Hamiltonian path in the comparability sense (tournament of forced order).

Worked Kahn sketch (diamond)

Vertices \(A,B,C,D,E\); arcs \(A\to C,B\to C,A\to D,B\to D,C\to E,D\to E\).
Initial indeg: \(A,B=0\); \(C,D=2\); \(E=2\).
Emit \(A\) then \(B\) (or \(B\) then \(A\)): after both, \(C,D\) indeg 0.
Emit \(C,D\) in either order; then \(E\).
All topos: orders with \(\{A,B\}\) before \(\{C,D\}\) before \(E\), and \(A,B\) free, \(C,D\) free—\(2\cdot 2=4\) topos.

Unique topological order

A DAG has a unique topological order iff there is a Hamiltonian path that forces every consecutive pair—equivalently, for every \(i\), the \(i\)-th vertex in the order is the unique source of the residual graph at that step (indegree-0 set always size 1).

Shortest path on DAG (preview Day 64)

Same topo DP as longest path but with \(\min\) instead of \(\max\), and \(d(\mathrm{source})=0\) (or \(w\) edges). One pass; handles negative edge weights because no cycles.

Tomorrow

Day 64 — Shortest paths: weights; Dijkstra idea + nonnegativity; Bellman-Ford awareness; triangle inequality; Dijkstra invariant sketch.

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

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