Network flow and shortest path problems use graphs to model roads, pipes, data links, schedules, and supply routes. This cheat sheet helps students turn real situations into vertices, edges, weights, capacities, sources, and sinks. It is useful for comparing routes, finding bottlenecks, and choosing an efficient algorithm instead of guessing by trial and error.
Key Facts
- A network is a graph with vertices connected by edges, and edges may have weights, directions, capacities, or costs.
- In a shortest path problem, the goal is to minimize the total path length, where total length = sum of edge weights along the path.
- Dijkstra's algorithm finds shortest paths from one start vertex when all edge weights are nonnegative.
- For Dijkstra's algorithm, once the smallest tentative distance is selected as permanent, that distance is final.
- A flow must satisfy capacity limits, so 0 <= flow on an edge <= capacity on that edge.
- Flow conservation means that for every intermediate vertex, total inflow = total outflow.
- The value of a flow is the total flow leaving the source, which equals the total flow entering the sink.
- The max-flow min-cut theorem states that maximum flow value = minimum cut capacity.
Vocabulary
- Vertex
- A point or node in a network that represents a location, station, event, or decision point.
- Edge
- A connection between two vertices that may represent a road, pipe, cable, task link, or allowed movement.
- Weight
- A number on an edge that measures distance, time, cost, risk, or another quantity to be minimized or compared.
- Capacity
- The maximum amount of flow that can pass through an edge.
- Source and Sink
- The source is where flow starts, and the sink is where the flow is collected or delivered.
- Cut
- A cut separates the source from the sink, and its capacity is the total capacity of edges crossing from the source side to the sink side.
Common Mistakes to Avoid
- Adding every edge connected to a route instead of only the edges actually traveled is wrong because a path total uses only the selected consecutive edges.
- Using Dijkstra's algorithm with negative edge weights is wrong because the algorithm assumes a permanent shortest distance cannot later be improved.
- Ignoring edge direction is wrong because a directed edge from A to B does not automatically allow travel or flow from B to A.
- Violating flow conservation at an intermediate vertex is wrong because flow cannot disappear or be created inside the network.
- Calling a cut minimum after checking only one separation is wrong because the minimum cut must have the smallest capacity among all valid source to sink cuts.
Practice Questions
- 1 A path from A to D uses edges with weights 6, 4, and 9. What is the total path length?
- 2 In a flow network, edges leaving the source carry flows 8, 5, and 7. What is the value of the flow?
- 3 A cut has crossing edge capacities 10, 6, 4, and 12. What is the capacity of the cut?
- 4 A road network has one route with fewer roads but heavy travel times and another route with more roads but smaller total time. Explain which route is shortest and why edge count alone is not enough.
Understanding Network Flow & Shortest Path
A useful model starts with careful choices. A vertex can represent a place, a machine, a person, or a stage in a process. An edge represents one allowed move or transfer.
Its number must match the quantity the problem cares about. For a delivery route, that might be travel time. For a phone network, it might be delay.
The shortest route is not always the route with the fewest edges. A path with three quick connections can beat one direct but slow connection.
Students should write down the meaning and units of every edge value before calculating. Mixing kilometres, minutes, and money in one total gives an answer with no clear meaning.
Shortest path methods work by keeping a best known distance to each vertex. At first, only the start has a distance of zero. Each time an edge is examined, the method tests whether going through the current vertex improves the recorded distance at the next vertex.
This is often called relaxing an edge. Dijkstra's method is efficient because it always works next on the unvisited vertex with the lowest current distance. Its logic depends on costs never dropping below zero.
A negative edge can make a route become cheaper after a supposedly final choice. In that case, Bellman Ford is safer because it repeatedly checks all edges for improvements. A reachable negative cycle means there is no finite shortest path, since a traveller could loop around it and reduce the total forever.
Flow problems need a different kind of thinking. The numbers on edges describe how much can pass, not how desirable a route is. Imagine a factory sending goods through several processing stations.
A narrow connection can limit the whole system even when most other connections have plenty of room. After sending some flow, it helps to draw the remaining capacity on each edge. This creates a residual network.
It includes forward room that is still unused. It can include backward room, which represents cancelling part of an earlier decision.
Backward edges matter because an early choice may block a better overall arrangement. Augmenting path methods increase the flow along a complete source to sink route, then update these remaining amounts until no such route exists.
A cut gives a strong way to explain why a maximum cannot be exceeded. It separates the source from the sink into two groups. Every edge crossing from the source side to the sink side forms a barrier.
Their combined capacity is an upper limit on any possible flow. If a proposed flow reaches that limit, it is proven optimal rather than merely looking good. This idea appears in internet bandwidth, evacuation planning, production limits, and assignment problems.
When learning, separate route questions from capacity questions. Check whether directions matter, whether an edge can be used more than once, and whether the task asks for one best path or the largest total transfer. A correct algorithm cannot repair a model that represents the situation incorrectly.