Lecture 11. Graph theory — algorithms #

11.1 Overview #

Lecture 10 developed the static language of graphs: vertices and edges, degrees, adjacency representations, weighted graphs, and the two coloring invariants — the chromatic number $\chi(G)$ (fewest colors for a proper vertex coloring) and the chromatic index $\chi'(G)$ (fewest colors for a proper edge coloring). That lecture told us what these quantities are; it did not tell us how to compute anything. This lecture is about doing things with graphs: first the two systematic traversals (breadth- and depth-first search) that visit every vertex, then five classical algorithms that produce colorings, shortest paths, and cheapest connecting networks, together with the data structures that make them fast and the proofs that make them trustworthy.

Three questions organize the chapter, each drawn from a real computational need.

1. How do we schedule conflicting tasks with as few resources as possible? This is graph coloring. We study greedy vertex coloring and greedy edge coloring — fast, simple heuristics that always produce a valid coloring and come with provable upper bounds on how many colors they use.
2. What is the cheapest way to get from one place to every other place? This is the single-source shortest-path problem, solved by Dijkstra’s algorithm when edge weights are non-negative.
3. What is the cheapest network that keeps everything connected? This is the minimum spanning tree problem, solved by Prim’s and Kruskal’s algorithms — two greedy routes to the same optimum, both justified by a single beautiful lemma, the cut property.

A recurring theme: greed #

Every optimization algorithm in this lecture is greedy (the two traversals, BFS and DFS, are the exception): it builds its answer incrementally and, at each step, commits to the choice that looks best right now, never reconsidering. Greedy algorithms are attractive because they are simple and fast, but the deep question is always the same:

Does taking the locally best choice at every step lead to a globally optimal result?

The answer here is instructive precisely because it is not uniform:

• For shortest paths and minimum spanning trees, greedy is exactly optimal, and we will prove it — via the “finalized-distance” invariant for Dijkstra and via the cut property for Prim and Kruskal.
• For coloring, greedy is only an approximation: it always yields a proper coloring, but may use more colors than the optimum $\chi(G)$ or $\chi'(G)$, and the number it uses depends on the order in which objects are processed.

Keeping this contrast in mind — when greed is provably safe and when it is merely a bounded heuristic — is one of the main takeaways of the lecture.

Prerequisites and notation #

We lean on the following from Lecture 10 (graph basics):

• A weighted graph attaches a real number $w(u,v)$ — a weight, cost, length, or capacity — to each edge.
• The adjacency list stores, for each vertex $v$, the list of its neighbors together with edge weights. It uses $O(n+m)$ space and lets us scan a vertex’s incident edges in time proportional to its degree. This is the representation assumed throughout. The alternative adjacency matrix costs $\Theta(n^2)$ space and is only competitive on very dense graphs.
• A proper coloring never gives the same color to two adjacent objects (adjacent vertices for vertex coloring; edges sharing an endpoint for edge coloring).
• $\Delta = \Delta(G)$ denotes the maximum degree of the graph, and $\deg(v)$ the degree of vertex $v$. Recall the Handshaking Lemma $\sum_v \deg(v) = 2m$.

We write $n = |V|$ for the number of vertices and $m = |E|$ for the number of edges. Inside asymptotic bounds we follow the standard convention (as in CLRS) of writing $V$ and $E$ for these counts, so that “$O(V+E)$” means “$O(n+m)$”; the letters name the sets, but in an $O(\cdot)$ they stand for the sizes. Spanning trees, forests, and the structural theory of trees are the subject of Lecture 12; we borrow two facts from there and flag them where used.

The running graph $G$ — defined and drawn in the next section — places $A$ at the far left, $F$ at the far right, and $B,C$ / $D,E$ as two middle columns, with every edge labelled by its weight. The single figure is reused for all five algorithms: coloring ignores the weights, the path/tree algorithms use them.

11.2 A word on greedy algorithms #

Before the graph algorithms, it helps to name the pattern they share.

Greedy algorithm — an algorithm that constructs a solution in a sequence of steps, and at each step irrevocably makes the choice that is locally optimal according to some fixed rule, without backtracking.

Two ingredients decide whether a greedy algorithm is correct (produces a globally optimal answer), rather than merely fast:

• The greedy-choice property: there is always a globally optimal solution that is consistent with the greedy first choice. (For MSTs this is exactly the cut property.)
• Optimal substructure: an optimal solution to the whole problem contains optimal solutions to subproblems, so that after making the greedy choice, solving the rest greedily still yields the optimum.

When both hold, an exchange argument (swap the greedy choice into an arbitrary optimal solution without making it worse) proves optimality. Shortest paths and MSTs enjoy both, which is why Dijkstra, Prim, and Kruskal are exact. Coloring lacks the greedy-choice property — the locally cheapest color can paint us into a corner — so greedy coloring is only a bounded approximation. (The deepest reason MST greed works is that the sets of “edges extendable to a spanning tree” form a matroid; matroids are exactly the structures on which greedy is always optimal. See Further reading.)

Remark. “Greedy” is a strategy, not a guarantee. The same word covers a provably optimal algorithm (Dijkstra) and a heuristic that can be arbitrarily far from optimal (greedy coloring on a bad ordering). Always ask which case you are in.

11.3 The running weighted graph #

To let the results be compared, we run Dijkstra, Prim, and Kruskal — and, ignoring the weights, both coloring algorithms — on one shared weighted graph $G=(V,E)$.

$$V=\{A,B,C,D,E,F\},$$

with the nine weighted edges

As adjacency lists (neighbors with weights):

$$\begin{aligned} A&:\{B(4),\,C(2)\} & B&:\{A(4),\,C(1),\,D(5)\} & C&:\{A(2),\,B(1),\,D(8),\,E(10)\}\\ D&:\{B(5),\,C(8),\,E(3),\,F(6)\} & E&:\{C(10),\,D(3),\,F(7)\} & F&:\{D(6),\,E(7)\} \end{aligned}$$

Degrees are $\deg(A)=2,\ \deg(B)=3,\ \deg(C)=4,\ \deg(D)=4,\ \deg(E)=3,\ \deg(F)=2$, so the maximum degree is $\Delta=4$ and (Handshaking check) $\sum_v\deg(v)=18=2\cdot 9=2m$. The graph is connected (needed for the MST algorithms) and its nine weights are distinct (which, as we prove later, makes the MST unique — so Prim and Kruskal must return the very same edge set, an ideal setup for comparison). It also contains several triangles ($ABC$, $BCD$, $CDE$, $DEF$), which will force at least three colors.

11.4 Graph traversal: breadth-first and depth-first search #

Before optimizing over a graph we must be able to visit it systematically — reach every vertex, discover the connected component of a start vertex, and build a tree of first-discoveries. The two canonical traversals differ only in the data structure that holds the frontier of discovered-but-unexplored vertices: a queue gives breadth-first search (BFS), a stack (or recursion) gives depth-first search (DFS).

BFS(G, s):                              DFS(G, s):          # recursive
    mark every vertex unvisited             mark s visited
    Q ← queue holding s;  visit s           for each neighbor w of s:
    while Q not empty:                          if w unvisited:
        u ← dequeue(Q)                              DFS(G, w)
        for each neighbor w of u:
            if w unvisited:
                visit w;  enqueue(Q, w)

DFS is usually written recursively — the call stack is the stack; an explicit-stack variant simply replaces BFS’s queue by a stack. Each vertex is enqueued once and each edge examined a constant number of times, so with adjacency lists both run in $O(|V|+|E|)$ — linear in the size of the graph.

Worked trace on $G$ (weights ignored), starting at $A$, neighbors in alphabetical order.

• BFS visits $A;\ B,C;\ D,E;\ F$ in rings of increasing distance from $A$. Its tree of discovery edges is $\{AB,AC,BD,CE,DF\}$, and the ring number is exactly the fewest-edges distance from $A$: $A{=}0,\ B{=}1,\ C{=}1,\ D{=}2,\ E{=}2,\ F{=}3$.
• DFS plunges $A\to B\to C\to D\to E\to F$, backtracking only at dead ends; its discovery tree is the path $\{AB,BC,CD,DE,EF\}$.

Same vertices, different trees — BFS stays shallow and wide, DFS goes deep.

What traversal is for.

• Connectivity and components. One traversal reaches exactly the start vertex’s component; restarting from any still-unvisited vertex counts the connected components (§10.9) in $O(|V|+|E|)$.
• Shortest paths in an unweighted graph. BFS’s ring number is the minimum number of edges from the source — the unweighted counterpart of Dijkstra below, and far cheaper when the weights are all equal.
• Paths and cycles. DFS underlies path-finding, cycle detection, and topological ordering; the findPath/findCircuit routines of Lab 6 are DFS at heart.

Traversal is the workhorse the rest of this chapter leans on: Dijkstra’s and Prim’s frontier-growing loops are BFS with a priority queue in place of a plain one.

11.5 Greedy vertex coloring #

Motivation #

Vertex coloring is the abstract form of conflict scheduling. Model each task as a vertex and join two tasks by an edge when they conflict (cannot share a resource). A proper coloring is then an assignment of resources — exam time slots, radio frequencies, CPU registers — such that no two conflicting tasks collide, and the number of colors is the number of resources needed. The classic compiler application is register allocation: variables are vertices, an edge means two variables are “live” simultaneously, colors are machine registers.

Finding $\chi(G)$ exactly is NP-hard, so in practice we reach for a fast heuristic. The simplest is greedy.

The algorithm #

Greedy vertex coloring — fix an ordering $v_1, v_2, \dots, v_n$ of the vertices; visit them in that order and give each vertex the smallest color (a positive integer $1, 2, 3, \dots$) not already used by any of its already-colored neighbors.

function GreedyVertexColoring(G, ordering v1..vn):
    for i = 1 to n:
        used ← { color[u] : u is a neighbor of vi and u already colored }
        color[vi] ← smallest positive integer not in used
    return color

Finding the smallest free color efficiently. Naively “scanning for a gap” sounds like it could be slow, but it is not. Keep a scratch boolean array seen[1..Δ+1]. When coloring $v_i$, for each already-colored neighbor $u$ with $\text{color}[u]\le \deg(v_i)+1$ set seen[color[u]] ← true; then scan $c = 1,2,\dots$ for the first index with seen[c] = false. Because $v_i$ has at most $\deg(v_i)$ colored neighbors, the answer is at most $\deg(v_i)+1$, so the scan stops within $\deg(v_i)+1$ steps. Reset only the entries you touched (or use a version-stamp trick) so the per-vertex cost stays $O(\deg(v_i))$.

Worked trace #

Run greedy on $G$ (ignoring weights) in the natural order $A,B,C,D,E,F$. The “colored neighbors” column lists each neighbor that is already colored and its color.

Colors used: $\{1,2,3\}$ — three colors. The final coloring is $A{=}1,\ B{=}2,\ C{=}3,\ D{=}1,\ E{=}2,\ F{=}3$; a quick check of all nine edges confirms every edge joins two differently colored endpoints, so it is proper.

Is three optimal? Yes: the triangle $A\text{–}B\text{–}C$ has three mutually adjacent vertices, all of which need distinct colors, so $\chi(G)\ge 3$; and greedy exhibited a proper $3$-coloring, so $\chi(G)=3$ and here greedy is optimal.

Correctness: greedy always produces a proper coloring #

Theorem 11.1. For every graph $G$ and every vertex ordering, GreedyVertexColoring returns a proper coloring.

Proof. Take any edge $uv \in E$; we must show $\text{color}[u]\ne\text{color}[v]$. Without loss of generality $u$ is colored before $v$ (one of them is). At the moment $v$ is colored, $u$ is an already-colored neighbor of $v$, so $\text{color}[u]$ lies in the set used that $v$ avoids. Hence $\text{color}[v]\ne\text{color}[u]$. As $uv$ was arbitrary, no edge is monochromatic. $\square$

Correctness: the $\Delta+1$ bound #

Theorem 11.2. GreedyVertexColoring uses at most $\Delta+1$ colors, for every ordering. Consequently $\chi(G)\le \Delta+1$.

Proof. When vertex $v_i$ is colored, the forbidden set used is contained in the set of colors of $v_i$’s already-colored neighbors, so $|\texttt{used}| \le \deg(v_i)\le\Delta$. Among the $\Delta+1$ colors $\{1,2,\dots,\Delta+1\}$ at most $\Delta$ are forbidden, so at least one is free; greedy picks the smallest free color, which is therefore $\le\Delta+1$. No vertex ever receives a color exceeding $\Delta+1$, so the total number of colors used is $\le\Delta+1$. Since the coloring is proper (Theorem 11.1), $\chi(G)\le\Delta+1$. $\square$

On $G$, $\Delta=4$, so the theorem promises $\le 5$ colors; greedy did much better with $3$ because the ordering was favorable.

Remark (Brooks’ theorem). The bound $\Delta+1$ is rarely tight. Brooks’ theorem (1941) states that a connected graph satisfies $\chi(G)\le\Delta$ unless $G$ is a complete graph $K_n$ (which needs $n=\Delta+1$) or an odd cycle (which needs $3=\Delta+1$). Our $G$ is neither, and indeed $\chi(G)=3\le\Delta=4$.

The ordering matters #

Theorem 11.2 bounds the worst case, but the actual number of colors depends heavily on the processing order. Greedy is always proper, yet the color count is not.

A concrete gap on $G$. Run greedy on the same graph $G$ in the order $A,E,B,D,C,F$:

This uses four colors, although $\chi(G)=3$. The culprit is vertex $C$: by the time it is reached, its four neighbors already carry three distinct colors $\{1,2,3\}$, forcing a fourth. Same graph, same algorithm, different order — one extra color.

A dramatic gap: the crown graph. The crown graph $S_n^0$ is $K_{n,n}$ with a perfect matching deleted: parts $\{x_0,\dots,x_{n-1}\}$ and $\{y_0,\dots,y_{n-1}\}$, with $x_i$ adjacent to every $y_j$ except $y_i$. It is bipartite, so $\chi=2$. But process the vertices in the paired order $x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}$: an easy induction shows $x_k$ and $y_k$ each see exactly the colors $\{1,\dots,k\}$ on already-colored neighbors and so receive color $k+1$. Greedy therefore uses $n$ colors on $2n$ vertices — arbitrarily far from the true value $2$. (For $n=3$ this already forces $3$ colors instead of $2$.) There is always an ordering achieving the optimum $\chi(G)$ — color the vertices in the order an optimal coloring would — but finding such an order is as hard as coloring itself.

The Welsh–Powell heuristic #

Since order is everything, a good default is to color high-degree vertices first, on the intuition that they are the hardest to satisfy and should be handled while colors are plentiful.

Welsh–Powell coloring — sort the vertices in non-increasing order of degree, then run greedy in that order.

function WelshPowell(G):
    sort vertices so that deg(v1) ≥ deg(v2) ≥ … ≥ deg(vn)
    return GreedyVertexColoring(G, v1..vn)

On $G$ the degrees are $C{:}4,\ D{:}4,\ B{:}3,\ E{:}3,\ A{:}2,\ F{:}2$, giving the order $C,D,B,E,A,F$:

Three colors — optimal. Welsh–Powell also yields the useful bound $\chi(G)\le \max_i \min\{\,d_i+1,\ i\,\}$, where $d_1\ge d_2\ge\cdots$ is the sorted degree sequence and $i$ is the position. It is a heuristic, not a guarantee: there exist graphs where even largest-degree-first is suboptimal. But it is cheap and usually good.

Complexity and data structures #

Data structure: adjacency lists plus one reusable scratch array seen[1..Δ+1].

Time: for each vertex $v_i$ we do $O(\deg(v_i))$ work (mark neighbor colors, scan for the first gap, reset). Summing over all vertices and using the Handshaking Lemma,

$$\sum_{i=1}^{n} O(\deg(v_i)) = O\!\Big(n + \sum_v \deg(v)\Big) = O(n + 2m) = O(V+E).$$

Welsh–Powell adds an $O(V\log V)$ sort, giving $O(V\log V + E)$. Space is $O(V)$ beyond the graph itself.

Common pitfall. Do not believe that greedy computes $\chi(G)$. It computes a proper coloring whose size is between $\chi(G)$ and $\Delta+1$, and which depends on the ordering. If you need the true chromatic number you must search (exponential in the worst case).

CS connection. Chaitin’s classic register allocator (1981) models allocation as vertex coloring of an interference graph and colors it greedily; when more than $k$ colors (= registers) are needed, some variable is “spilled” to memory — the practical response to greedy’s non-optimality.

11.6 Greedy edge coloring #

Motivation #

Edge coloring is the natural model for timetabling round-robin schedules. Represent players (or teams, machines, people) as vertices and each required match/meeting as an edge; a color is a time slot. Two edges sharing an endpoint must get different colors (a player cannot play two matches at once), so a proper edge coloring is a conflict-free schedule and $\chi'(G)$ is the fewest time slots needed.

The algorithm #

Greedy edge coloring — fix an ordering of the edges; give each edge the smallest color not used by any adjacent edge (an edge that shares an endpoint) that is already colored.

function GreedyEdgeColoring(G, ordering e1..em):
    for k = 1 to m:
        let ek = (u, v)
        used ← { color[e] : e already colored and e shares endpoint u or v with ek }
        color[ek] ← smallest positive integer not in used
    return color

This is literally greedy vertex coloring run on the line graph $L(G)$, whose vertices are the edges of $G$ and whose edges join pairs of $G$-edges that share an endpoint. Every theorem about greedy vertex coloring transfers, with $\Delta(L(G))$ in place of $\Delta(G)$.

Worked trace #

Color $G$ processing edges in the order $AB, AC, BC, BD, CD, CE, DE, DF, EF$. Recall $\Delta(G)=4$.

Four colors. The four color classes are

$$1:\{AB,CD,EF\}\quad 2:\{AC,BD\}\quad 3:\{BC,DE\}\quad 4:\{CE,DF\},$$

and each is a matching (no two of its edges share a vertex; the formal treatment and Hall’s theorem are in Lecture 12 §12.9) — which is exactly what “proper edge coloring” means. Class $1$ is even a perfect matching, pairing up all six vertices. Since $\chi'(G)\ge\Delta=4$ (the four edges at $C$ must all differ), greedy’s four colors are optimal here: $\chi'(G)=4$.

Correctness and bounds #

Theorem 11.3 (proper). GreedyEdgeColoring always returns a proper edge coloring. Proof. It is Theorem 11.1 applied to the line graph $L(G)$: two edges sharing an endpoint are adjacent vertices of $L(G)$, and the algorithm gives them different colors by the same argument. $\square$

Theorem 11.4 (the $2\Delta-1$ bound). GreedyEdgeColoring uses at most $2\Delta-1$ colors. Proof. An edge $e=uv$ is adjacent to at most $(\deg u-1)+(\deg v-1)\le 2\Delta-2$ other edges, hence to at most $2\Delta-2$ already-colored ones. Among the colors $\{1,\dots,2\Delta-1\}$ at least one is free, and greedy takes the smallest such. $\square$

How good is $2\Delta-1$? Compare it with the optimum, pinned down by a famous theorem from Lecture 10.

Vizing’s theorem. Every simple graph satisfies $\chi'(G)\in\{\Delta,\ \Delta+1\}$.

So the true optimum is one of just two values, whereas greedy only promises $2\Delta-1$ — off by nearly a factor of two in the worst case. On $G$ greedy happened to hit the optimum $\Delta=4$, but in general greedy edge coloring is a weaker approximation than the theory allows.

Complexity #

Data structure: adjacency lists plus a scratch array of size $2\Delta$.

Time: for edge $e=uv$ we scan its $\le 2\Delta-2$ adjacent edges and find the smallest free color in $O(\Delta)$. Summed over all edges,

$$\sum_{uv\in E}\big(\deg u+\deg v\big) = \sum_v \deg(v)^2 \le \Delta\sum_v\deg(v)=2\Delta m,$$

so the total is $O(E\cdot\Delta)$. Space $O(V+E)$.

Common pitfall. “Adjacent” for edge coloring means sharing an endpoint, not being consecutive in the input list. An edge must avoid the colors of edges at both of its endpoints.

11.7 Dijkstra’s shortest-path algorithm #

Motivation and the problem #

Given a weighted graph and a start vertex, we want the cheapest route to everywhere else: the single-source shortest-path problem. This is the computational core of GPS navigation, packet routing (the link-state protocol OSPF runs Dijkstra), network latency analysis, and countless planning tasks.

Shortest-path distance — write $\delta(s,v)$ for the minimum weight of any path from the source $s$ to $v$ (and $\delta(s,v)=\infty$ if $v$ is unreachable). A shortest path is a path achieving this minimum.

Dijkstra’s algorithm finds $\delta(s,v)$ for every $v$ in a graph whose edge weights are all non-negative. It maintains a tentative distance $\text{dist}[v]$ for each vertex — the length of the best route to $v$ found so far — repeatedly finalizes the unfinished vertex of smallest tentative distance, and then relaxes that vertex’s edges.

Relaxation — for an edge $(u,v)$: if $\text{dist}[u] + w(u,v) < \text{dist}[v]$, a shorter route to $v$ through $u$ has been found, so update $\text{dist}[v] \leftarrow \text{dist}[u] + w(u,v)$ and set $\text{prev}[v]\leftarrow u$ (recording the predecessor, so paths can be reconstructed).

Pseudocode #

function Dijkstra(G, w, s):
    for each vertex v in G:
        dist[v] ← ∞
        prev[v] ← undefined
    dist[s] ← 0
    Q ← min-priority queue of all vertices, keyed by dist
    while Q is not empty:
        u ← extract-min(Q)                 # closest not-yet-finalized vertex
        for each neighbor v of u:
            alt ← dist[u] + w(u, v)
            if alt < dist[v]:              # relaxation
                dist[v] ← alt
                prev[v] ← u
                decrease-key(Q, v, alt)
    return dist, prev

Once a vertex is extracted from $Q$, its distance is final and never changes again — the crux of the correctness proof below.

Worked trace #

Run Dijkstra on $G$ from source $A$. Each row shows the tentative-distance array after one more vertex has been finalized; the Chosen column names the vertex just extracted (with its now-final distance), and a dash “$-$” means “not yet reached” ($\infty$).

Reading the steps (bold entries mark a strict improvement by relaxation):

• Step 1 — extract $A$ (dist $0$); relax its edges, giving $B=4$ and $C=2$.
• Step 2 — the smallest tentative distance is $C=2$; finalize it and relax $C$’s edges. Edge $C\text{–}B$ gives $2+1=3<4$, so $B$ improves from $4$ to $3$ (the route $A\to C\to B$ beats the direct edge $A\to B$). Also $D=2+8=10$ and $E=2+10=12$.
• Step 3 — extract $B=3$; relax $B\text{–}D$: $3+5=8<10$, so $D$ improves to $8$ (route $A\to C\to B\to D$). ($B$’s only neighbors are $A,C,D$, so $E$ is untouched here.)
• Step 4 — extract $D=8$; relax $D\text{–}E$: $8+3=11<12$, so $E$ improves to $11$; relax $D\text{–}F$: $F=8+6=14$.
• Step 5 — extract $E=11$; relax $E\text{–}F$: $11+7=18 > 14$, no improvement — the longer route is correctly rejected.
• Step 6 — extract $F=14$; nothing left to improve. Done.

Final distances from $A$: $A{=}0,\ B{=}3,\ C{=}2,\ D{=}8,\ E{=}11,\ F{=}14$. Three separate vertices ($B$, $D$, $E$) had their distances improved after first being reached — the essence of relaxation — and $F$’s tempting-but-worse route through $E$ was discarded.

Path reconstruction. Follow $\text{prev}$ backward from the target. For $F$: $\text{prev}[F]=D,\ \text{prev}[D]=B,\ \text{prev}[B]=C,\ \text{prev}[C]=A$, giving the shortest path $A\to C\to B\to D\to F$ of length $2+1+5+6=14$. The $\text{prev}$ pointers of all vertices together form the shortest-path tree rooted at $A$.

Correctness #

Two elementary facts first, then the main theorem.

Lemma A (upper-bound property). At all times $\text{dist}[v]\ge\delta(s,v)$, and once $\text{dist}[v]$ is finite it is the length of some actual $s$–$v$ path. Proof. Initially $\text{dist}[s]=0=\delta(s,s)$ and all others are $\infty$. Relaxation only ever sets $\text{dist}[v]=\text{dist}[u]+w(u,v)$, which is the length of the path to $u$ (a real path, inductively) extended by edge $(u,v)$; and no real path can be shorter than the minimum $\delta(s,v)$. $\square$

Lemma B (subpath optimality). If $s=x_0,x_1,\dots,x_k$ is a shortest path, then each prefix $x_0,\dots,x_j$ is a shortest path to $x_j$, so $\delta(s,x_j)+w(x_j,x_{j+1})= \delta(s,x_{j+1})$. Proof. A cheaper route to a prefix endpoint could be spliced in to beat the whole path, contradicting its optimality. $\square$

Theorem 11.5 (Dijkstra correctness). When Dijkstra extracts a vertex $u$ from $Q$, its distance is correct: $\text{dist}[u]=\delta(s,u)$. Hence all final distances are correct.

Proof (by contradiction on the extraction order). Suppose not, and let $u$ be the first vertex extracted with $\text{dist}[u]\ne\delta(s,u)$. By Lemma A, $\text{dist}[u]\ge \delta(s,u)$, so in fact $\text{dist}[u]>\delta(s,u)$. Note $u\ne s$ (since $\text{dist}[s]=0 =\delta(s,s)$ and $s$ is extracted first, correctly), and $\delta(s,u)<\infty$ (otherwise $\text{dist}[u]=\infty=\delta(s,u)$), so a shortest path $P$ from $s$ to $u$ exists.

Let $S$ be the set of vertices already finalized (extracted) just before $u$ is extracted. Then $s\in S$ but $u\notin S$, so $P$ starts inside $S$ and ends outside it. Walk along $P$ and let $y$ be the first vertex on $P$ that is not in $S$, and let $x$ be its predecessor on $P$ (so $x\in S$; possibly $x=s$).

Claim: $\text{dist}[y]=\delta(s,y)$. Since $x\in S$, $x$ was extracted before $u$, and by our choice of $u$ as the first bad vertex, $\text{dist}[x]=\delta(s,x)$ held at $x$’s extraction. At that moment we relaxed edge $(x,y)$, so afterward $\text{dist}[y]\le\text{dist}[x]+w(x,y)=\delta(s,x)+w(x,y)$. By Lemma B (as $x,y$ are consecutive on the shortest path $P$), $\delta(s,x)+w(x,y)=\delta(s,y)$. Thus $\text{dist}[y]\le\delta(s,y)$, and with Lemma A, $\text{dist}[y]=\delta(s,y)$, proving the claim.

Now $y$ lies on $P$ at or before $u$, and the piece of $P$ from $y$ to $u$ has non-negative total weight (this is the only place non-negativity is used!), so $\delta(s,y)\le\delta(s,u)$. Chaining the (in)equalities,

$$\text{dist}[y]=\delta(s,y)\le\delta(s,u)<\text{dist}[u].$$

But both $y$ and $u$ are in $Q$ when the algorithm chose to extract $u$ by minimum tentative distance, forcing $\text{dist}[u]\le\text{dist}[y]$ — contradicting $\text{dist}[y]<\text{dist}[u]$. No such $u$ exists, so every extraction is correct. $\square$

Why non-negativity is essential. The single step $\delta(s,y)\le\delta(s,u)$ assumes the $y\to u$ portion of $P$ costs $\ge 0$. A negative edge breaks this, and Dijkstra can finalize a vertex too early.

Common pitfall — negative weights. Consider the directed graph $A\to B$ ($w=2$), $A\to C$ ($w=3$), $C\to B$ ($w=-2$). Dijkstra extracts $A$, sets $\text{dist}[B]=2,\ \text{dist}[C]=3$, then extracts and finalizes $B$ at $2$ (it is the smallest), before ever examining $C$. But the true shortest route is $A\to C\to B$ with length $3+(-2)=1$. Dijkstra never revisits a finalized vertex, so it reports $\text{dist}[B]=2$ — wrong. (If $B$ had any outgoing edge, the premature value $2$ would propagate, corrupting descendants too.) For graphs with negative edge weights use the Bellman–Ford algorithm, which relaxes every edge $V-1$ times in $O(VE)$ and, on a $V$-th pass that still improves something, detects a negative-weight cycle (on which no shortest path exists).

Complexity #

The running time depends entirely on the priority queue. Let $T_{\text{ex}}$ and $T_{\text{dk}}$ be the costs of extract-min and decrease-key. There are $V$ extractions and at most $E$ decrease-keys (one per relaxation), giving $O(V\cdot T_{\text{ex}} + E\cdot T_{\text{dk}})$.

(*amortized.) The workhorse is the binary heap, an array-embedded complete binary tree in which every node’s key is $\le$ its children’s; insert, decrease-key, and extract-min each cost $O(\log V)$ by sifting an element up or down one tree level at a time. For a connected graph $E\ge V-1$, so $O((V+E)\log V)=O(E\log V)$.

Remark (lazy deletion). Many implementations skip decrease-key: on each relaxation they simply push a new $(\text{dist},v)$ pair and, on extraction, discard any pair whose key exceeds the current $\text{dist}[v]$. The heap may hold up to $E$ entries, but since $\log E\le\log V^2=2\log V$, the bound is still $O(E\log V)$. This trades a little memory for much simpler code and is what most standard libraries do.

Common pitfall. Do not “update in place then forget to re-heapify.” Either call a real decrease-key, or use lazy deletion and check for stale entries at extraction — otherwise the queue’s min is wrong.

CS connection. Dijkstra is the basis of link-state routing (OSPF, IS-IS) and of the “uniform-cost search” in AI; adding a goal-directed heuristic turns it into the A* search algorithm used in games and mapping.

11.8 Minimum spanning trees and the cut property #

The problem #

Anticipating Lecture 12: a spanning tree of a connected graph $G$ is a subgraph that is a tree (connected, acyclic) and includes every vertex; it necessarily has exactly $n-1$ edges. A minimum spanning tree (MST) is a spanning tree of least total edge weight. MSTs answer “what is the cheapest set of links that keeps the whole network connected?” — laying cable, roads, or pipelines; they also seed clustering algorithms and give a $2$-approximation for the metric traveling-salesman problem.

Both algorithms that follow are greedy, and both are proved correct by a single lemma. To state it we need the vocabulary of cuts.

Cut. A cut $(S,\ V\setminus S)$ is a partition of the vertices into two nonempty parts. Crossing edge. An edge crosses the cut if it has one endpoint in $S$ and the other in $V\setminus S$. Light edge. A crossing edge of minimum weight is a light edge of the cut. Respecting a cut. A set of edges $A$ respects the cut if no edge of $A$ crosses it. Safe edge. An edge $e$ is safe for $A$ if $A\subseteq$ (some MST) implies $A\cup\{e\}\subseteq$ (some MST).

The cut property #

Theorem 11.6 (Cut Property). Let $A$ be a set of edges contained in some MST of $G$. Let $(S,V\setminus S)$ be any cut that $A$ respects, and let $e$ be a light edge crossing this cut. Then $e$ is safe for $A$.

Proof (exchange argument). Let $T$ be an MST with $A\subseteq T$. If $e\in T$ we are done, since then $A\cup\{e\}\subseteq T$. So suppose $e=(u,v)\notin T$, with $u\in S$ and $v\in V\setminus S$.

Adding $e$ to the tree $T$ creates exactly one cycle $\mathcal C$ (a fundamental fact about trees, Lecture 12: any two vertices already have a unique path in $T$, and $e$ closes it into a cycle). Traversing $\mathcal C$, we start at $u\in S$, use $e$ to reach $v\in V\setminus S$, and eventually return to $u$; since each crossing switches sides and we must end where we began, $\mathcal C$ crosses the cut an even number of times. It crosses once at $e$, so it crosses at least once more, at some edge $e'\ne e$.

This $e'$ is not in $A$: it crosses the cut, but $A$ respects the cut (no $A$-edge crosses). Now exchange: set $T' = (T\setminus\{e'\})\cup\{e\}$. Removing $e'$, an edge on the cycle $\mathcal C$, keeps $T'$ connected; it still has $n-1$ edges, so $T'$ is a spanning tree. Its weight is

$$w(T') = w(T) - w(e') + w(e).$$

Because $e$ is a light (minimum-weight) crossing edge and $e'$ also crosses, $w(e)\le w(e')$, so $w(T')\le w(T)$. But $T$ is an MST, so $w(T')\ge w(T)$; hence $w(T')=w(T)$ and $T'$ is also an MST. Finally $A\subseteq T'$ (we removed $e'\notin A$ and added $e$) and $e\in T'$, so $A\cup\{e\}\subseteq T'$: the edge $e$ is safe. $\square$

Theorem 11.7 (Cycle Property). For any cycle $\mathcal C$ in $G$, if $e$ is a strict-maximum-weight edge of $\mathcal C$, then $e$ belongs to no MST. Proof. If some MST $T$ contained $e$, deleting $e$ splits $T$ into two components; the rest of the cycle $\mathcal C\setminus\{e\}$ is a path joining $e$’s endpoints, so it contains some edge $e'$ crossing that split with $w(e')<w(e)$. Then $(T\setminus\{e\})\cup\{e'\}$ is a spanning tree of smaller weight — contradiction. $\square$

The cut property tells us which edges to include; the cycle property tells us which to exclude. Prim and Kruskal are the two ways to apply the first; Kruskal also uses the second to justify skipping edges.

Corollary 11.8 (uniqueness). If all edge weights are distinct, the MST is unique. Proof. In Theorem 11.6 with distinct weights, a light edge $e\notin T$ would give $w(e)<w(e')$ strictly, hence $w(T')<w(T)$, contradicting that $T$ is an MST — so every MST contains every light edge of every cut, pinning down one tree. $\square$

Because our running graph $G$ has distinct weights, its MST is unique, and Prim and Kruskal must produce identical edge sets, not merely equal weights.

11.9 Prim’s algorithm #

Idea and pseudocode #

Prim’s algorithm grows a single tree outward from a start vertex. It keeps the set of tree vertices and, at every step, adds the cheapest edge crossing from the tree to a vertex not yet in it. Each vertex $v$ outside the tree stores $\text{key}[v]$, the weight of the cheapest known edge connecting it to the current tree, and a priority queue delivers the global minimum.

function Prim(G, w, s):
    for each vertex v:
        key[v] ← ∞          # cheapest known edge connecting v to the tree
        parent[v] ← undefined
        inMST[v] ← false
    key[s] ← 0
    Q ← min-priority queue of all vertices, keyed by key
    while Q is not empty:
        u ← extract-min(Q)
        inMST[u] ← true
        for each neighbor v of u:
            if not inMST[v] and w(u, v) < key[v]:
                key[v] ← w(u, v)
                parent[v] ← u
                decrease-key(Q, v, key[v])
    return { (v, parent[v]) : v ≠ s }      # the MST edges

Worked trace #

Run Prim on $G$ from $A$. Each row shows the $\text{key}[\,]$ array after one extraction; “$\ast$” marks a vertex now in the tree, and bold marks a key just improved. The Added edge is $(\text{parent}[u],u)$ for the extracted $u$.

Narration:

• Step 1 — from $A$, keys of $B,C$ become $4,2$.
• Step 2 — extract $C$ (key $2$, cheapest), add $A\text{–}C$. Relaxing $C$’s edges drops $\text{key}[B]$ from $4$ to $1$ (edge $B\text{–}C$), and sets $\text{key}[D]=8,\ \text{key}[E]=10$.
• Step 3 — extract $B$ (key $1$), add $C\text{–}B$. Edge $B\text{–}D$ drops $\text{key}[D]$ from $8$ to $5$.
• Step 4 — extract $D$ (key $5$), add $B\text{–}D$. Edge $D\text{–}E$ drops $\text{key}[E]$ from $10$ to $3$, and $\text{key}[F]=6$.
• Step 5 — extract $E$ (key $3$), add $D\text{–}E$. Edge $E\text{–}F$ has weight $7>6$, so $\text{key}[F]$ is unchanged.
• Step 6 — extract $F$ (key $6$), add $D\text{–}F$. Tree complete.

MST edges: $\{A\text{–}C,\ B\text{–}C,\ B\text{–}D,\ D\text{–}E,\ D\text{–}F\}$; total weight $2+1+5+3+6 = \mathbf{17}$. Five edges for six vertices — a valid spanning tree. Notice Prim added the weights in the order $2,1,5,3,6$: it takes the cheapest frontier edge, which is generally not the globally cheapest remaining edge (contrast Kruskal).