Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 68 ยท Graph Theory

Shortest Paths, Matching and Flows

Learn weighted shortest paths with Dijkstra, bipartite matching with Hall's theorem, and max-flow min-cut with Edmonds-Karp, all in short Python code.

So far edges have only been present or absent. Real networks attach numbers to them: kilometers on a road, milliseconds on a link, gigabits per second on a cable. Three classic questions arise. What is the cheapest route between two points? How can we pair up two groups (workers and jobs, students and projects) so that as many people as possible get a partner? How much traffic can a network carry from a source to a destination?

These questions look unrelated, but they share tools. This lesson recaps shortest paths with Dijkstra's algorithm, studies bipartite matching and the exact condition for a perfect assignment (Hall's theorem), and then introduces maximum flow, whose famous dual statement (max-flow equals min-cut) also solves matching. Every algorithm is short enough to fit in one code block.

Three questions on weighted graphs

Shortest path What is the cheapest route from A to B?
Matching Pair up two groups with no one used twice.
Max flow How much can pass from source to sink?
1 / 2

Weighted graphs and shortest paths

In a weighted graph each edge has a number, the weight. The length of a path is the sum of its edge weights, and the shortest path is the one with the least total. When all weights are equal, BFS finds it (see Paths, Cycles and Connectivity). With non-negative varied weights, Dijkstra's algorithm does the job.

The idea: keep a tentative distance for every vertex (infinity at first, 0 at the source). Repeatedly take the unfinished vertex with the smallest distance; its distance is now final, because every other route to it would first have to pass through a vertex at least as far away, and weights are not negative. Then relax its outgoing edges: if going through it gives a neighbor a shorter route, update the neighbor. A priority queue makes picking the smallest vertex fast. Full details and complexity are in Dijkstra's Algorithm and Shortest Path Variants, including what to do with negative weights.

Python Dijkstra with route reconstruction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cheapest route to B goes A -> C -> B for a cost of 3, beating the direct edge of 4. Fewest edges is not the same as least cost.

Matching in bipartite graphs

A matching is a set of edges, no two sharing a vertex. A maximum matching has as many edges as possible; a perfect matching covers every vertex. In a bipartite graph with groups L (say, workers) and R (jobs), a matching is an assignment where each worker takes at most one job and each job goes to at most one worker.

To find a maximum matching, use augmenting paths. Given the current matching, an augmenting path starts at an unmatched vertex in L, alternates between non-matching and matching edges, and ends at an unmatched vertex in R. Flipping every edge along the path (matched becomes unmatched and vice versa) increases the matching size by one. Berge's theorem says a matching is maximum exactly when no augmenting path exists. The simple recursive method below (often called Kuhn's algorithm) tries to place each worker, re-routing earlier workers when needed.

Hall's marriage theorem

When can every worker get a job? Looking at any group S of workers, the jobs they can do together, the neighborhood N(S), must contain at least |S| jobs, or those workers fight over too few. Hall's theorem says this necessary condition is also sufficient: a matching covering all of L exists if and only if |N(S)| โ‰ฅ |S| for every subset S of L. The brute-force check below tries all subsets, which is fine for small groups and shows which subset breaks the condition when the matching fails.

Python Maximum matching and Hall's condition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the second case ann and ben both qualify only for web, so the pair {ann, ben} has a single neighbor and Hall's condition fails. In fact only two jobs exist between all four workers, so the algorithm matches 2 of the 4. Hall's condition pinpoints a concrete bottleneck group instead of just saying "no".

Maximum flow and minimum cut

A flow network is a directed graph in which each edge has a capacity, with a source s where flow begins and a sink t where it ends. A flow assigns each edge an amount that does not exceed its capacity, and at every other vertex what flows in equals what flows out (conservation). The goal is a flow of maximum value, the total leaving s.

The method is again to augment. The residual graph records how much more each edge can carry, plus a reverse edge for each flow already sent, which allows us to "undo" earlier decisions. Find any path from s to t in the residual graph with spare capacity, push as much as the narrowest edge allows, and repeat. Choosing the path with the fewest edges (BFS) gives the Edmonds-Karp algorithm, which always terminates in polynomial time.

When no augmenting path remains, let S be the set of vertices still reachable from s in the residual graph. The edges leaving S are all full, and together they form a cut: a way of separating s from t. Any flow must cross every cut, so no flow can exceed the capacity of any cut. This is the max-flow min-cut theorem: the maximum flow value equals the minimum capacity of an s-t cut. The algorithm hands you both numbers at once.

Python Edmonds-Karp: maximum flow and the minimum cut

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For this network the maximum flow is 12. The minimum cut separates {s, a, b} from the rest and consists of the edges a-c (5), a-t (4) and b-d (3). Notice that the source edges (capacity 18 in total) are not the bottleneck; the cut deeper inside the network is.

Matching is a flow problem

Max flow solves bipartite matching too. Add a source with an edge of capacity 1 to every worker, an edge of capacity 1 from every job to a new sink, and give each worker-job edge capacity 1. Whole-number capacities guarantee a whole-number maximum flow, and the saturated middle edges are exactly a maximum matching. Applying the min-cut theorem to this network gives Konig's theorem: in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Python Bipartite matching as a flow problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which tool for which question?

  • Cheapest route, non-negative weights: Dijkstra. With negative weights, Bellman-Ford; for all pairs, Floyd-Warshall.
  • Assignments between two groups: bipartite matching (Kuhn's method for small cases, Hopcroft-Karp for large ones), with Hall's theorem telling you whether a full assignment can exist.
  • Capacity and bottleneck questions: max flow, whose min-cut tells you the cheapest set of links to cut or strengthen.
  • Spanning everything cheaply rather than going from A to B: a minimum spanning tree, from Trees and Spanning Trees.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does Dijkstra's algorithm require non-negative edge weights?

    Dijkstra finalizes the closest unfinished vertex, assuming any other route is at least as long. A negative edge can break that assumption.
  2. 2. What does Hall's theorem say about a bipartite graph with groups L and R?

    Hall's condition |N(S)| >= |S| for every subset S of L is necessary and sufficient for a matching that saturates L.
  3. 3. Three workers can all only do the same two jobs. What is the largest possible matching among them?

    Each job goes to at most one worker, and there are only two jobs, so at most 2 workers are matched.
  4. 4. What does the max-flow min-cut theorem state?

    No flow can exceed any cut, and the augmenting-path algorithm finds a flow and a cut with exactly the same value.
  5. 5. Why does the residual graph contain reverse edges?

    A reverse edge with capacity equal to the current flow lets an augmenting path push flow back, undoing an earlier choice.

Summary

  • Dijkstra's algorithm finds shortest paths from one source in graphs with non-negative weights, using a priority queue and edge relaxation.
  • A matching uses no vertex twice; augmenting paths grow a matching until none is left, which proves it is maximum (Berge).
  • Hall's theorem: a bipartite graph has a matching covering group L exactly when every subset S of L has at least |S| neighbors.
  • Max flow is computed by repeatedly augmenting along residual paths (Edmonds-Karp uses BFS); the final residual graph reveals a minimum cut with the same value.
  • Bipartite matching is max flow on a unit-capacity network; Konig's theorem links maximum matchings and minimum vertex covers.

Next: Graph Isomorphism and Drawing Graphs, which asks when two graphs are really the same.