Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 49 ยท Network Optimization

Chapter 4 Review: Network Optimization

Review Chapter 4: shortest paths, minimum spanning trees, maximum flow, transportation and assignment, with a decision table, a code recap and ten quiz questions.

Chapter 4 introduced the algorithms that make network problems easy: Dijkstra for shortest paths, Kruskal and Prim for spanning trees, augmenting paths for maximum flow, and network LPs for transportation and assignment. This review puts them on one page, lets you run all of them on one network, and checks your understanding with ten mixed questions. The chief skill to practice is recognition: given a story, decide which network problem it is.

One-page summary of the five network problems with the question each answers, its algorithm and the example result
Chapter 4 in one picture: five questions, five algorithms and the answers from our examples: 13 km, cost 16, flow 11, cost 450 and 32 hours.

What you will learn

  • A recap of every lesson in Chapter 4.
  • How to pick the right problem type for a story.
  • How to run all the algorithms with the same few lines of scipy.

Key terms

Shortest path: least-weight route. Spanning tree: connects all nodes with no cycles.

Max flow: largest amount from source to sink. Min cut: the bottleneck whose capacity equals the max flow.

Transportation problem: ship from sources to destinations at minimum cost. Assignment problem: one-to-one matching at minimum cost.

Recap table

Lesson Question Algorithm Example answer
Overview Nodes, arcs, weights Adjacency matrix and list Delivery network, 41 km of road
Shortest path Cheapest route S to T Dijkstra (nonnegative weights) 13 km via S, B, A, C, D, T
Spanning tree Connect everything cheaply Kruskal or Prim Cost 16, five cables
Maximum flow How much can pass Augmenting paths, min cut Flow 11 = cut 6 + 5
Transportation and assignment Ship or match at least cost Network LP, Hungarian algorithm $450 and 32 hours

Which problem is it?

The story says It is a...
"fastest route", "least toll", "cheapest connection from A to B" Shortest path
"connect all sites", "lay cable or pipe to every village" Minimum spanning tree
"how many cars per hour", "maximum data rate", "bottleneck" Maximum flow and minimum cut
"ship from plants to warehouses", "supply and demand" Transportation
"one worker per job", "match each X to one Y" Assignment
"route with a side limit, such as at most 3 tolls" LP or integer program (no longer a pure shortest path)

Practice: all four algorithms on one network

The block below treats the delivery network of Lesson 1 as a road map (for shortest path and spanning tree) and then as a pipe system (for maximum flow, with the weights as capacities, directed from S to T).

Python Run the Chapter 4 toolkit on one network

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 shortest-path length and the spanning-tree cost are both 13 here by coincidence: in this particular network the shortest-path tree from S happens to be a minimum spanning tree as well. In general the two differ (see the spanning-tree lesson).

Flashcards: Chapter 4 terms

Three short case studies

A courier chooses a route. A van must go from the depot to a customer. The road lengths are known, none is negative, and the driver wants the least distance. This is a shortest path problem. Run Dijkstra's algorithm, or call scipy.sparse.csgraph.dijkstra, then follow the predecessors back from the customer. If the manager adds "avoid more than two toll roads", the pure structure is gone: use a constrained model (an LP or integer program) with a variable for each road.

A utility wires a new town. There are eight neighbourhoods and a list of possible cable links with their costs. Every neighbourhood must be reachable, but nobody cares about the route any signal takes. This is a minimum spanning tree. Kruskal's method sorts the links and adds each one that does not close a loop. The result has seven cables, one fewer than the number of neighbourhoods, and no cheaper set of seven can connect them all.

A distributor wants to know its limit. Goods go from a plant through hubs to a port, and each road or rail link can carry only so many pallets a day. The question "how many pallets can we move?" is a maximum flow, and the augmenting-path method answers it. The minimum cut names the links that limit the system, so the manager knows which one to widen first. Widening any other link changes nothing.

Notice how each story began with a plain-language question and ended with a standard model. Practicing this recognition is the best preparation for the chapters that follow, where networks reappear in scheduling, queueing and project planning.

Common misconceptions

"All network problems are the same problem." They share structure, but the objective differs: shortest path minimizes one route, a spanning tree minimizes total cable, a flow maximizes throughput.

"Add a side constraint and the fast algorithm still works." A side constraint such as a limit on the number of tolls usually destroys the special structure and may need integer programming.

"Greedy always works on networks." It is optimal for Dijkstra (nonnegative weights) and spanning trees, but not for flows (reverse arcs are needed) or many other problems.

Check your understanding

Quick check ยท 10 questions

of 10 answered You scored / 10 ยท perfect!

  1. 1. A telecom firm must connect every village at least total cable cost. Which problem is this?

    Connecting all nodes with the cheapest set of edges is the minimum spanning tree problem.
  2. 2. Which algorithm settles the unsettled node with the smallest tentative distance?

    That is Dijkstra's greedy step.
  3. 3. How many edges does a spanning tree on 10 nodes have?

    n โˆ’ 1 = 9.
  4. 4. In the example network, the shortest route from S to T is...

    The route S, B, A, C, D, T has length 2 + 1 + 5 + 2 + 3 = 13.
  5. 5. What does the capacity of a minimum cut equal?

    That is the max-flow min-cut theorem.
  6. 6. Why are reverse arcs used in the residual network?

    Pushing flow on a reverse arc undoes some earlier flow.
  7. 7. Total supply is 120 and total demand is 100. How can the transportation problem be balanced?

    The dummy destination absorbs the surplus supply.
  8. 8. For the 4-by-4 assignment example, what is the minimum total time?

    A-4, B-1, C-3, D-2 gives 11 + 6 + 6 + 9 = 32.
  9. 9. Why do transportation LPs have integer optimal solutions for integer supplies and demands?

    Total unimodularity makes all corner points integer.
  10. 10. You must find the best route but also limit it to at most 2 toll roads. What is the best approach?

    The side constraint breaks the pure shortest-path structure.

Summary

  • Five network problems: shortest path, minimum spanning tree, maximum flow with minimum cut, transportation and assignment.
  • Recognizing the problem type from the story is half the work.
  • Dijkstra, Kruskal and Prim are greedy and fast; flows use augmenting paths with reverse arcs; transportation and assignment are network LPs with integer solutions.
  • Our examples: shortest route 13 km, spanning tree cost 16, maximum flow 11, shipping cost $450, assignment 32 hours.
  • Side constraints usually require integer programming.

Next: Chapter 5 Overview: Inventory and Scheduling