ETF2480 Chap.6 Shortest Paths and Maximum Flow
Shortest Paths and Maximum Flow
Shortest path and maximum flow share directed networks and node conservation but answer different questions. A shortest-path model sends one unit from source to sink and minimises total arc length, time or cost. A maximum-flow model sends a variable total and maximises throughput while respecting arc capacities. Flow may split across routes, so it is not simply a path with larger numbers.
Cuts create upper bounds on total flow; when a feasible flow equals a cut capacity, optimality is certified. These models reward careful attention to arrow direction, node balance, selected arcs, bottlenecks and the distinction between route cost and throughput.
What this chapter covers
- 01
Directed arcs and reachability
- 02
Source, intermediate and sink balance
- 03
Shortest-path objective
- 04
Maximum-flow capacity
- 05
Source-to-sink cuts
- 06
Bottleneck interpretation
Worked example · free
Find the least-cost directed route
- +1List the valid routes S-A-T, S-B-T and S-B-A-T.
- +2Their costs are 9, 10 and 2 + 1 + 3 = 6.
- +2Select arcs S-B, B-A and A-T; node balance is zero at B and A.
- +1Report shortest-path cost 6 and preserve the stated arc directions.
Key terms
- Shortest path
- A source-to-sink route minimising the sum of selected arc weights.
- Maximum flow
- The greatest feasible source-to-sink throughput subject to conservation and arc capacities.
- Arc capacity
- An upper bound on the amount of flow that can use a directed arc.
- Network cut
- A partition separating source from sink whose crossing capacity bounds total flow.
- Bottleneck
- A limiting arc or cut whose capacity restricts further throughput.
Shortest Paths and Maximum Flow FAQ
What is the main difference between path and flow?
A shortest path selects one route for a unit and minimises total weight. Maximum flow maximises a total quantity that may divide across several routes and recombine. The source and sink equations therefore contain different objective logic.
How does a cut prove maximum flow?
Any source-to-sink flow must cross every separating cut, so the sum of forward capacities on a cut is an upper bound. If a feasible flow achieves that same number, the flow and cut together certify optimality.
Which arc should receive more capacity?
Expand an arc only after identifying the current minimum-cut structure. Increasing a busy arc outside every limiting cut may leave maximum throughput unchanged. Re-solve after a capacity change because the bottleneck can move to another cut.
How can a maximum flow be certified?
Exhibit a feasible flow and a source-to-sink cut with the same value. The flow proves attainability, the cut supplies an upper bound, and equality establishes optimality for the stated network.
Exam move
Use two colours when drawing a network: one for direction and capacity or cost, another for the chosen path or realised flow. For shortest path, write one-unit source and sink balances and zero balances at intermediate nodes, then recompute the selected arc weights. For maximum flow, write an unknown total t in the source and sink equations, check every arc capacity and sum flows through intermediate nodes.
Practise finding a small cut and comparing its capacity with a proposed flow. Create paired questions on the same diagram, one asking for shortest route and another for maximum throughput, to make the objective distinction automatic. In every conclusion, name whether the result is a cost, a route, a total flow or a bottleneck.
Build an arc ledger with tail, head, direction, weight and capacity columns so reverse travel is never assumed accidentally. For route solutions, trace continuously from source to sink and reject disconnected selected arcs even if their total cost is low. For flow solutions, reconcile every intermediate node and calculate total source outflow independently from sink inflow.
Draw at least two source-side cuts and sum only forward arcs crossing toward the sink; compare the smallest capacity with the achieved flow. Change one capacity inside a minimum cut and predict whether another cut becomes limiting. Contrast this with increasing an arc outside every current minimum cut.
Practise translating a time-expanded replacement problem into nodes and directed transitions, because the network may represent states rather than geography. End by stating whether integrality comes from network structure or from an explicit discrete requirement.
Working through Shortest Paths and Maximum Flow in ETF2480? Sia is AskSia’s AI Management tutor — ask any ETF2480 Shortest Paths and Maximum Flow question and get a clear, step-by-step explanation grounded in how ETF2480 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
