Skip to content

Quiz 5: All-Pairs Paths, Flow, Matching

Monday, November 23 · Dr. Engel · covers C22–C24 (CLRS 23.1–23.2, 24.1–24.3, 25.2)

What the quiz will look like

Expect four or five short problems worth 20–25 points each, all worked by hand. Quizzes 2 and 3 (and, from memory, Quiz 4) never asked for a proof. They asked you to run the first step or two of an algorithm on a tiny input, to fill in a missing piece, or to read an algorithm's output table and say what it means. The formula is often printed right on the quiz ("Recall m[i,j] = …"), so the points go to people who can apply it quickly and without slips. Every section below is built around that: one idea, one step-through figure, then a Try-it in the quiz's format.

The likeliest questions, best bets first:

  • Floyd-Warshall: given D(k−1), write D(k) (or fill in its blanks).
  • Ford-Fulkerson: given a flow, draw the residual graph, pick the augmenting path, and apply it, including canceling flow on a backward edge.
  • Bipartite matching: turn the graph into a flow network and run Ford-Fulkerson with a fixed rule for choosing paths.
  • Gale-Shapley: trace the proposals from preference lists; spot a blocking pair.
  • Repeated "squaring": compute L(2) (or one row of it) from L(1), and know it stops changing at L(n−1).
  • Fixing a flow network: antiparallel edges, several sources/sinks, vertex capacities.
  • Quick facts that fit in a sentence: running times, what Π means, why path choice matters for Ford-Fulkerson, who Gale-Shapley favors.

All-pairs shortest paths

Single-source shortest paths (Bellman-Ford, Dijkstra) answer "how far is everything from s?" All-pairs answers it for every starting vertex at once, so the answer is a whole table: the entry in row i, column j is the shortest distance from i to j.

Three matrices

Everything in this chapter is a matrix with one row and one column per vertex.

  • W, the weights. The graph itself: wij is the weight of edge i→j, 0 on the diagonal, and ∞ where there's no edge.
  • The answer, D (or L). dij is the weight of a shortest path from i to j. It plays the role of v.d from single-source.
  • Π, the predecessors. πij is the vertex just before j on a shortest path from i. NIL on the diagonal and where there's no path. It plays the role of v.π.

The largest finite entry of the answer matrix is the graph's diameter: the worst-case shortest trip (longest message delay, longest drive for an ambulance).

Figure 1 runs Floyd-Warshall (next section) on the lecture's six-vertex graph; for now just look at the first and last steps. Row b ends up all ∞ because b has no outgoing edges. The largest entry, 14 (a→f and c→d), is the diameter.

Reading a path out of Π

Π stores only the last hop, so you rebuild a path backwards. To get the path from i to j: look up πij (call it x), so the path ends x→j. Then look up πix, and so on until you reach i.

For a 4-vertex graph, Floyd-Warshall produced this Π. What is the shortest path from 3 to 1?

Π 1 2 3 4
1 NIL 3 1 2
2 4 NIL 4 2
3 4 3 NIL 2
4 4 3 4 NIL

Stay in row 3 the whole time (the source never changes). π31 = 4, so the path ends 4→1.

π34 = 2, so before 4 comes 2: …2→4→1. Then π32 = 3, which is the source, so stop. Path: 3 → 2 → 4 → 1.

Watch out

Don't switch rows as you walk back. It's always row i (the source); only the column changes.

Build paths up one edge at a time: L®

The first method (CLRS 23.1) grows paths by number of edges. Let L® hold the shortest distances using at most r edges.

  • L(1) = W, since one edge is just the edges themselves.
  • To get L®, try extending every best (r−1)-edge path by one more edge:

lij® = min over all k of ( lik(r−1) + wkj )

In words: go from i to some k the best way you already know, then take the single edge k→j. Keep the cheapest.

This has exactly the shape of matrix multiplication, row i of L times column j of W, except that each "multiply" becomes + and the "sum" becomes min. That's why the textbook calls it matrix "multiplication." Step through it on the lecture's graph:

When to stop. Without negative cycles, a shortest path never repeats a vertex, so it has at most n − 1 edges. That means L(n−1) is the final answer, and every later matrix equals it: L(n) = L(n−1) = … (the last step of Figure 2 shows L(5) = L(4)).

Speed. Each "multiplication" is three nested loops, Θ(n³). Doing n − 2 of them (SLOW-APSP) is Θ(n⁴). Since the matrices stop changing anyway, you can overshoot and square repeatedly, L(1) → L(2) → L(4) → L(8) …, which needs only about lg n multiplications: Θ(n³ lg n) (FASTER-APSP).

Here is W for a 4-vertex graph (it is also L(1)). Compute row 1 of L(2).

W 1 2 3 4
1 0 4 1 ∞
2 ∞ 0 ∞ 1
3 ∞ 2 0 6
4 3 ∞ −2 0

Row 1 of L(1) is (0, 4, 1, ∞). Pair it with each column of W, add, take the min:

  • l11 = min(0+0, 4+∞, 1+∞, ∞+3) = 0
  • l12 = min(0+4, 4+0, 1+2, ∞+∞) = 3 (1→3→2)
  • l13 = min(0+1, 4+∞, 1+0, ∞−2) = 1
  • l14 = min(0+∞, 4+1, 1+6, ∞+0) = 5 (1→2→4)

Row 1 of L(2) = (0, 3, 1, 5).

Is l14 = 5 final? No: L(3) allows three edges, and 1→3→2→4 costs 1 + 2 + 1 = 4. You're only guaranteed done at L(n−1) = L(3).

Floyd-Warshall

Floyd-Warshall is also dynamic programming, but it grows paths by which vertices they may pass through, not by how many edges they use. Number the vertices 1…n. Then

dij(k) = the shortest i→j distance when every stop between i and j comes from {1, 2, …, k}.

  • D(0) = W. No stops allowed, so only direct edges count.
  • D(n) is the answer. Every vertex is allowed as a stop.

One more waypoint

Going from D(k−1) to D(k) adds vertex k as a possible stop. A best i→j path either skips k (nothing changes) or passes through k once: the best way from i to k, then the best way from k to j, both using only the old stops. Keep whichever is cheaper:

dij(k) = min( dij(k−1),  dik(k−1) + dkj(k−1) )

In Figure 3, each step shades row k and column k of the old matrix. Those are the only numbers you need: cell (i, j) is compared with (row i's entry in column k) + (column j's entry in row k).

Shortcuts for doing it by hand

A quiz question will hand you D(k−1) and ask for D(k). These cut most of the work:

  • Row k and column k never change in step k, and neither does the diagonal (it stays 0). Copy them straight over.
  • If dik = ∞, row i can't change. You can't reach k from i yet, so there's nothing to add.
  • If dkj = ∞, column j can't change, for the same reason.
  • For each cell left, add its row's column-k number to its column's row-k number, and write the smaller of that and the old value.

Updating Π. If a cell improved, the new path ends with k's path to j, so copy πkj from the old Π (row k, same column). If the cell didn't improve, πij stays.

Here is D(2) for a 4-vertex graph. Write D(3).

D(2) 1 2 3 4
1 0 4 1 5
2 ∞ 0 ∞ 1
3 ∞ 2 0 3
4 3 7 −2 0

Copy what can't change. Row 3, column 3 and the diagonal stay. Row 2 has d23 = ∞, so row 2 stays. Column 1 has d31 = ∞, so column 1 stays. That leaves d12, d14, d42 and d44 (the diagonal, so it stays too).

Check the rest against (column 3 of its row) + (row 3 of its column):

  • d12: min(4, d13 + d32 = 1 + 2) = 3
  • d14: min(5, d13 + d34 = 1 + 3) = 4
  • d42: min(7, d43 + d32 = −2 + 2) = 0
D(3) 1 2 3 4
1 0 3 1 4
2 ∞ 0 ∞ 1
3 ∞ 2 0 3
4 3 0 −2 0

Watch out

Read every number from the old matrix D(k−1), not from the one you're filling in, and remember ∞ + anything is still ∞ (even ∞ + a negative number).

Running time, and the two methods side by side

FLOYD-WARSHALL is three nested loops (k outside, then i, then j) around one O(1) line, so it's Θ(n³). It allows negative edges, as long as there are no negative cycles.

Method Grows paths by Time
Repeated L® (SLOW-APSP) one more edge per step Θ(n⁴)
Repeated squaring (FASTER-APSP) doubling the edge count Θ(n³ lg n)
Floyd-Warshall one more allowed stop per step Θ(n³)

Transitive closure: who can reach whom

Sometimes you only care whether j is reachable from i. That's the transitive closure. Run the same loops on 1s and 0s:

  • tij(0) = 1 if i = j or there's an edge i→j, otherwise 0.
  • tij(k) = tij(k−1) OR ( tik(k−1) AND tkj(k−1) )

So min becomes OR and + becomes AND. Bit operations are a little faster in practice, but it's still Θ(n³).

Edges: 4→1, 2→4, 2→3, 3→2, 4→3. Which row of the transitive closure T is different from the others, and why?

Row 1 is (1, 0, 0, 0). Vertex 1 has no outgoing edges, so it reaches only itself. Rows 2, 3 and 4 are all 1s: 2 and 3 reach each other, 2 reaches 4, and 4 reaches 1 and 3.

Flow networks

Shortest paths treat an edge as a route you might take. Flow treats every edge as a pipe that is carrying something all at once, at some rate: water through pipes, cars on roads, packets on links, goods through a supply chain. Stuff leaves a source s, moves through the network, and arrives at a sink t. The question is how much can get through per unit of time.

The setup

A flow network is a directed graph where each edge u→v has a capacity c(u, v) ≥ 0, the most it can carry (an edge that isn't there has capacity 0). The textbook's rules also require:

  • No antiparallel edges. Never both u→v and v→u (fixes below).
  • One source and one sink, and every vertex lies on some path from s to t.

A flow puts an amount f(u, v) on each edge, and it must obey two rules:

  • Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v). No pipe overflows.
  • Flow conservation: at every vertex except s and t, flow in = flow out. Nothing piles up or leaks.

The value of the flow, |f|, is what leaves the source (minus anything flowing back into it). The maximum-flow problem asks for the flow with the largest |f|.

In Figure 4, what is |f|? Then check conservation at v₂.

|f| = 11 + 8 = 19, the flow on the two edges leaving s. (The flow into t is 15 + 4 = 19 too, as it must be.)

Into v₂: 8 (from s) + 4 (from v₃) = 12. Out of v₂: 1 (to v₁) + 11 (to v₄) = 12. Balanced.

Bending a messy problem into a valid network

Real problems often break the rules. Each break has a standard fix that doesn't change the maximum flow.

Antiparallel edges. If you have both v₁→v₂ (capacity 10) and v₂→v₁, split one of them with a new vertex v′: v₁→v′ and v′→v₂, both with the old capacity.

→

Several sources or sinks. Add a supersource s with an edge of capacity ∞ to each original source, and a supersink t with an ∞ edge from each original sink. The ∞ edges never limit anything; they just give the problem one entry and one exit.

Vertex capacities. If a vertex v itself can pass at most l(v), split it into v (in) and v′ (out) joined by one edge v→v′ with capacity l(v). Edges that entered v still enter v; edges that left v now leave v′. Each vertex adds one vertex and one edge, so G′ has 2|V| vertices and |E| + |V| edges.

→

Ford-Fulkerson

The obvious idea: find any s→t path that still has room, push as much as fits, and repeat. That alone can get stuck below the maximum, because an early path can use an edge that a better arrangement needed. Ford-Fulkerson fixes this by also letting a later path push flow backwards along an edge, undoing part of an earlier choice. The residual graph keeps track of both options.

The residual graph Gf

For every edge u→v carrying f out of capacity c, Gf gets up to two edges:

  • Forward u→v with c − f: the room left. Leave it out when the edge is full (c − f = 0).
  • Backward v→u with f: the flow that could be sent back (undone). Leave it out when f = 0.

Then:

  1. An augmenting path is any simple path from s to t in Gf.
  2. Its bottleneck cf(p) is the smallest residual on the path.
  3. Augment: add the bottleneck to every forward edge on the path. For a path edge that runs backwards against an original edge, subtract it from that edge's flow. That subtraction is called cancellation.
  4. Rebuild Gf and repeat. When Gf has no s→t path, the flow is maximum.

Figure 6 picks up the Figure 4 flow and does one round. The path's middle edge, v₂→v₃, exists only as a back edge, so pushing along it cancels flow on v₃→v₂.

You can also see this flow is maximum straight from G: v₁→v₃, v₄→v₃ and v₄→t are all full, and every route to t has to cross one of them, so 12 + 7 + 4 = 23 is all that can ever get through.

Choosing paths: Ford-Fulkerson vs Edmonds-Karp

Ford-Fulkerson is a method, not a fully specified algorithm: it says "find a path" without saying which one. The choice matters a lot:

  • Edmonds-Karp is Ford-Fulkerson that always takes the augmenting path with the fewest edges, found by breadth-first search in Gf. That guarantees at most O(VE) augmentations, each found in O(E), so O(VE²) overall. (The lecture slide says "O(|V||E|)": that's the bound on the number of augmentations.)
  • With arbitrary choices and integer capacities, the time is O(E·|f*|), which grows with the size of the answer (as in Figure 7). With irrational capacities, a bad sequence might never finish.

Here is Edmonds-Karp on the lecture network, starting from zero flow. Ties between equally short paths can go either way; this one takes the vertices in order s, v₁, v₂, v₃, v₄, t.

Capacities: s→a 4, s→b 3, a→b 3, a→t 2, b→t 5. The current flow is 3 along s→a→b→t, and 0 everywhere else.

(1) Draw Gf. (2) Run Edmonds-Karp to the end: give each path, its bottleneck, and the final |f|.

Gf: s→a 1 and back a→s 3; a→b is full, so only the back edge b→a 3; b→t 2 and back t→b 3; s→b 3 and a→t 2 are untouched.

Paths, shortest first:

  1. s→a→t, bottleneck min(1, 2) = 1
  2. s→b→t, bottleneck min(3, 2) = 2
  3. s→b→a→t, bottleneck min(1, 3, 1) = 1. It runs b→a against a→b, so a→b drops from 3 to 2 (cancellation).

Final |f| = 7, which also equals the total capacity out of s (4 + 3), so nothing more could fit. Step through it:

Watch out

  • A full edge has no forward residual, only a back edge. An empty edge has no back edge.
  • The bottleneck is the smallest number in Gf along the path, not the smallest capacity in G.
  • On a back edge, flow goes down on the original edge.

Bipartite matching

A graph is bipartite when its vertices split into two sets, L and R, and every edge goes between L and R (never within a side). Think tasks and machines, students and projects, shirts and pants.

  • A matching is a set of edges where no vertex is used twice.
  • A maximum matching is a matching with as many edges as possible.

The trick is that you already know how to solve this: it's a max-flow problem in disguise.

  1. Add a source s with an edge s→ℓ to every left vertex.
  2. Add a sink t with an edge r→t from every right vertex.
  3. Direct every original edge left → right.
  4. Give every edge capacity 1.

Run Ford-Fulkerson. Each augmenting path adds one matched pair, and the middle edges carrying flow at the end are the maximum matching. Capacity 1 on s→ℓ means each left vertex sends at most one unit, so it's matched at most once (same for r→t on the right).

Watch iteration 2 in Figure 9: L2's first choice, R1, is already taken, so the search tries going R1 → L1 along a back edge, which would bump L1 off R1. L1 has nowhere else to go, so that branch dead-ends and the path uses R3 instead. When such a re-route does succeed, an earlier match gets swapped out for two new ones. That's cancellation doing the work.

Path rules on a quiz

A quiz has to pin down which path you pick so there's one right answer, for example "choose the alphabetically earliest path." Search in that order: from s try the first left vertex, from there the first right vertex, and back up only when you hit a dead end. Leave s and t out when spelling the path.

Left: a, b, c. Right: x, y, z. Edges: a–x, a–y, b–x, c–y, c–z. Build the flow network and run Ford-Fulkerson, always taking the alphabetically earliest path. List each path and the final matching.

  1. a→x
  2. b's only edge is to x, which is taken, so try the back edge x→a, then a→y: b→x→a→y. a gives x to b and moves to y.
  3. c→y is taken, so c→y→a? a's only other option is x, and x is taken by b, a dead end. Next is c→z.

Matching: {a–y, b–x, c–z}, size 3, so everyone is matched.

Stable marriage

Plain matching only asks whether a pair is allowed. The stable-marriage problem (CLRS 25.2) adds preferences:

  • Both sides have n members, and anyone can be paired with anyone on the other side.
  • Each person ranks everyone on the other side, best to worst. Rankings don't have to agree: x can love a while a ranks x last.
  • Everyone must be paired.

A pair (p, q) who are not matched to each other is a blocking pair if p prefers q to p's partner, and q prefers p to q's partner. They'd both ditch their partners for each other. A matching with no blocking pair is stable.

Checking for a blocking pair

For each person p, look at everyone p ranks above their current partner. For each such q, ask whether q also ranks p above q's partner. One yes is a blocking pair; if there's never a yes, the matching is stable. Both halves have to hold. One side wanting a swap isn't enough.

Gale-Shapley

One side proposes and the other side accepts or rejects:

  1. Everyone starts free.
  2. While someone on the proposing side is free, that person proposes to the next person on their list they haven't proposed to yet.
  3. The one proposed to:
    • is free: accepts. They're now engaged.
    • prefers the new proposer to their current partner: drops the partner (who becomes free again) and accepts.
    • prefers their current partner: rejects.
  4. When nobody is free, the engagements are the answer.

Once someone on the accepting side is engaged, they stay engaged and only ever trade up. Proposers only ever move down their lists.

The order in which free proposers go doesn't change the result (Figure 10 always lets the alphabetically first free proposer go next, which matches the lecture). What's worth knowing:

  • It always ends, with a stable matching. So a stable matching always exists.
  • At most n² proposals, since each of n proposers goes through a list of n at most once: O(n²).
  • The proposing side does better. Each proposer ends up with the best partner they could have in any stable matching. The accepting side gets the worst it could get. Swap roles and you may get a different stable matching.
  • Stable doesn't mean "best overall." There can be several stable matchings, and Gale-Shapley returns the one that favors the proposers.

Proposers a, b, c and acceptors x, y, z rank (best first):

a x y z
b x z y
c y x z
x b a c
y a c b
z a b c

(1) Is the matching {a–x, b–y, c–z} stable? (2) Run Gale-Shapley with a, b, c proposing.

(1) Not stable. b is with y but ranks x higher, and x ranks b above its partner a. So (b, x) is a blocking pair.

(2) a→x accepted. b→x: x prefers b, drops a. a→y accepted. c→y: y prefers a, rejects. c→x: x prefers b, rejects. c→z accepted. Result {a–y, b–x, c–z} after 6 proposals.