Paths, Flows and Network Optimization

Introduction and Context

Many computational problems are naturally represented as networks. A road system connects locations, a communication system connects devices, a supply chain connects suppliers to customers, and a machine-learning pipeline connects data-processing stages. In each case, the entities are modeled as vertices and the relationships between them as edges. Algorithms for paths, flows, and network optimization provide systematic methods for finding efficient routes, allocating limited capacity, matching resources, and identifying structural weaknesses.

This chapter develops the principal algorithmic frameworks for network optimization: shortest paths, maximum flow, minimum-cost flow, bipartite matching, and related optimization methods. The emphasis is on modeling decisions, correctness, computational complexity, implementation issues, and applications in artificial intelligence and machine learning.

Learning Objectives

After completing this chapter, a student should be able to:

1. Model practical systems using directed, undirected, weighted, and capacitated graphs.
2. Distinguish between shortest-path, flow, cut, matching, and network-design problems.
3. Select and analyze Dijkstra’s, Bellman–Ford, Floyd–Warshall, and related algorithms.
4. Explain residual networks, augmenting paths, max-flow min-cut duality, and flow conservation.
5. Apply Ford–Fulkerson, Edmonds–Karp, Dinic’s algorithm, and minimum-cost-flow methods.
6. Formulate bipartite matching as a flow problem and recognize its AI applications.
7. Evaluate complexity, numerical assumptions, scalability, and implementation risks.
8. Analyze an applied network-optimization case and justify an algorithmic design.

1. Graph Models for Network Optimization

A graph is written as G = (V,E), where V is a set of vertices and E is a set of edges. Let n = |V| and m = |E|. An edge may be directed, such as (u,v), or undirected, such as {u,v}. A weighted graph associates a numerical value w(u,v) with each edge.

Common interpretations include:

A path is a sequence of vertices connected by edges. A path is simple if it does not repeat vertices. A cycle begins and ends at the same vertex. In a directed graph, edge direction must be respected.

A graph may be represented by an adjacency matrix or adjacency lists. An adjacency matrix requires Θ(n²) storage and gives constant-time edge lookup. Adjacency lists require Θ(n+m) storage and are usually preferable for sparse networks. Priority-queue shortest-path algorithms generally benefit from adjacency lists.

2. Shortest-Path Problems

The single-source shortest-path problem asks for the minimum path distance from a source vertex s to every reachable vertex. If a path P contains edges with weights w(e), its length is

The formula assumes additive edge weights. The shortest-path distance from s to v is

If no path exists, the distance is conventionally +∞. In practical systems, weights may represent time, distance, energy, monetary cost, or a transformed score. The interpretation must be consistent: adding travel times is meaningful, whereas multiplying unrelated probabilities may require a different model.

2.1 Relaxation

The fundamental operation is relaxation. Suppose the current estimate of the distance to v is d[v]. For an edge (u,v) with weight w(u,v), relaxation tests whether reaching v through u is better:

A predecessor π[v] is updated when the estimate improves. Initially, d[s] = 0 and all other estimates are +∞. The predecessor pointers reconstruct a shortest-path tree.

2.2 Dijkstra’s Algorithm

Dijkstra’s algorithm repeatedly selects the unsettled vertex with the smallest tentative distance and relaxes its outgoing edges. Its correctness depends critically on the condition that all edge weights are non-negative:

With a binary heap and adjacency lists, the running time is O((n+m) log n). With a simple array it is O(n²), which may be competitive for dense graphs. With specialized heaps, better theoretical bounds are possible, but implementation complexity and constant factors matter.

Pseudocode

Dijkstra(G, s)
    for each vertex v:
        d[v] ← ∞; predecessor[v] ← NIL
    d[s] ← 0
    Q ← all vertices keyed by d
    while Q is not empty:
        u ← Extract-Min(Q)
        for each edge (u, v) of u:
            if d[v] > d[u] + w(u,v):
                d[v] ← d[u] + w(u,v)
                predecessor[v] ← u
                Decrease-Key(Q, v)

Dijkstra’s algorithm is invalid when negative edges exist because a vertex believed to be final may later be improved through a negative edge.

2.3 Bellman–Ford Algorithm

Bellman–Ford solves the single-source problem even when edge weights are negative. It performs relaxation over all edges n−1 times. A simple path has at most n−1 edges, so any shortest simple path is covered. Its time complexity is O(nm).

After the main passes, a further successful relaxation indicates a reachable negative-weight cycle. Such a cycle makes the shortest-path problem undefined for vertices reachable from it, because repeatedly traversing the cycle can reduce path cost without bound.

Bellman–Ford is slower than Dijkstra’s algorithm but is useful for currency-arbitrage detection, potential-based optimization, and graphs containing penalties or rewards represented by negative weights.

2.4 All-Pairs Shortest Paths

The Floyd–Warshall algorithm computes distances between every ordered pair of vertices. Let D^(k)[i,j] denote the shortest distance from i to j using only vertices numbered from 1 through k as intermediate vertices. The recurrence is

The final matrix is obtained after k = n. The algorithm requires Θ(n³) time and Θ(n²) space when implemented in place. It permits negative edges but not negative cycles if meaningful finite distances are required.

For sparse graphs or a small number of sources, repeated single-source algorithms may be preferable. Floyd–Warshall is attractive when the graph is dense, the network is small or medium-sized, and all-pairs information is required.

2.5 Worked Shortest-Path Example

Consider directed edges:

Starting at A, initial distances are d(A)=0 and all others infinity. Relaxing from A gives d(B)=4 and d(C)=2. From C, the route C→B gives 2+1=3, improving B from 4 to 3; C→D gives 9. From B, B→D gives 3+3=6, improving D from 9 to 6, and B→E gives 11. From D, D→E gives 6+2=8, improving E to 8. Thus the shortest path from A to E is A→C→B→D→E, with total cost 8.

3. Network Flows

A flow network is a directed graph with a source s, a sink t, and non-negative capacities c(u,v). A feasible flow f(u,v) satisfies two conditions.

Capacity constraint

Flow conservation for every vertex other than the source and sink:

The value of a flow is the net flow leaving the source:

The maximum-flow problem seeks a feasible flow of greatest value. Capacities may represent bandwidth, production capacity, vehicle throughput, or the number of assignments permitted by a resource.

3.1 Residual Networks and Augmenting Paths

Given a flow, the residual capacity of a forward edge is c(u,v)−f(u,v). A reverse edge records the ability to cancel previously assigned flow and has residual capacity f(u,v). The residual network therefore contains alternatives for revising earlier decisions.

An augmenting path is an s–t path in the residual network. If its bottleneck residual capacity is

then the flow can be increased by Δ. Repeating this operation produces a maximum flow under the standard Ford–Fulkerson conditions.

3.2 Ford–Fulkerson and Edmonds–Karp

Ford–Fulkerson repeatedly searches for an augmenting path. With integer capacities and appropriate path selection, each augmentation increases the integral flow by at least one. Its running time is O(m|f^*|), where |f^*| is the maximum flow value, for integer capacities. This is a pseudo-polynomial bound, not a polynomial bound in the bit length of the input.

Edmonds–Karp selects augmenting paths by breadth-first search, thereby choosing a path with the fewest edges. It runs in O(nm²), independent of the numerical magnitude of capacities. This makes it theoretically more robust, although faster algorithms are usually used for large networks.

3.3 Dinic’s Algorithm

Dinic’s algorithm constructs a level graph using breadth-first search and then sends a blocking flow through that graph. For general networks its time complexity is O(n²m). Important special cases have stronger bounds, including improved performance on unit-capacity networks and bipartite matching instances.

The algorithm is widely used in practice because it combines a strong worst-case foundation with efficient implementations. Careful use of adjacency arrays and explicit reverse-edge indices is essential.

3.4 Max-Flow Min-Cut Theorem

An s–t cut is a partition (S,T) of the vertices such that s ∈ S and t ∈ T. Its capacity is

The max-flow min-cut theorem states:

Every feasible flow is bounded above by every cut capacity, because all flow crossing from S to T must pass through cut edges. When no augmenting path remains in the residual network, the vertices reachable from s define a cut whose capacity equals the current flow value, proving optimality.

The theorem has both algorithmic and managerial meaning. A minimum cut identifies a bottleneck: a small set of links whose expansion could increase total throughput.

4. Worked Maximum-Flow Example

Suppose a source S connects to A and B with capacities 10 and 8. A connects to B with capacity 2 and to T with capacity 6. B connects to T with capacity 10.

One possible sequence is:

1. Send 6 units along S→A→T.
2. Send 8 units along S→B→T.
3. Send the remaining 4 units from S→A to B, but A has only 4 units remaining after sending 6, while B→T has 2 units remaining. Therefore only 2 additional units can be sent through A→B→T.

The total flow is 16. The source capacity is 18, but the sink-side edges A→T and B→T have total capacity 16. The cut separating {S, A, B} from {T} has capacity 6+10=16. Since a flow of 16 equals the cut capacity, it is maximum.

This example illustrates why individual edge capacities cannot be analyzed independently: the value is determined by the interaction of multiple paths and bottlenecks.

5. Minimum-Cost Flow

Maximum flow maximizes quantity, but many applications also require minimizing cost. Each edge has a capacity and a per-unit cost cst(u,v). For a flow f, total cost is

The minimum-cost-flow problem seeks a feasible flow satisfying specified supply and demand while minimizing this expression. Costs may represent transportation expense, energy consumption, latency, or risk.

A common method repeatedly finds a minimum-cost augmenting path in the residual network. Reverse edges receive negative cost, because canceling a previous unit reverses its cost. The successive-shortest-path method is especially useful when the required flow is moderate. Potentials can reweight residual edges so that Dijkstra’s algorithm becomes applicable even when reverse edges have negative reduced costs.

For a potential function π, the reduced cost is

If potentials maintain non-negative reduced costs on residual edges, Dijkstra’s algorithm can be used safely. The original and reduced-cost shortest paths differ by a constant for fixed endpoints, so optimality is preserved.

Minimum-cost flow can also be formulated as a linear program. For each edge, the decision variable is flow, the capacity constraints bound the variable, and conservation constraints define feasible routing. Network matrices have special integrality properties: with integer capacities and supplies, an optimal basic solution can be chosen integral under standard formulations. This explains why many network-allocation problems do not require general-purpose integer programming.

6. Bipartite Matching as Network Optimization

A bipartite graph has vertex sets L and R, with edges only between the two sets. A matching is a set of edges sharing no endpoints. In a maximum bipartite matching problem, the objective is to maximize the number of matched pairs.

Construct a flow network by adding:

• a source connected to every vertex in L with capacity 1;
• an edge of capacity 1 for every permissible pair between L and R;
• an edge of capacity 1 from every vertex in R to the sink.

Every unit of integral flow corresponds to one matching pair. Thus maximum matching can be solved by a maximum-flow algorithm. For large bipartite graphs, the Hopcroft–Karp algorithm achieves O(m√n) time and is often preferable to generic flow.

Applications include assigning students to projects, workers to shifts, machines to jobs, and detected objects to predicted objects in computer vision. Weighted matching extends the model when pairings have scores or costs.

7. Network Design and Other Optimization Problems

Not every network problem is a path or flow problem.

Minimum Spanning Trees

For an undirected connected weighted graph, a minimum spanning tree connects all vertices with minimum total edge weight and no cycle. Kruskal’s algorithm sorts edges and uses a disjoint-set data structure, running in O(m log m). Prim’s algorithm grows a tree from a starting vertex and runs in O(m log n) with a binary heap and adjacency lists.

Spanning trees model infrastructure design, such as laying cables or connecting facilities. Unlike shortest paths, a spanning tree optimizes total connection cost rather than the route between one source and one destination.

Multi-Commodity Flow

A single-commodity flow has one source–sink requirement. In multi-commodity flow, several demands compete for shared capacities. If f_k(u,v) is the flow for commodity k, the shared capacity constraint is

The problem is substantially harder; integral versions are generally NP-hard. Linear programming, approximation algorithms, decomposition, and heuristics are common. This distinction is important in communication and logistics systems where independent routes cannot be optimized separately.

Resource-Constrained Shortest Paths

If a route must minimize cost while respecting time, energy, or risk limits, the problem becomes a constrained shortest-path problem. Such variants may be NP-hard, even though ordinary shortest path is polynomial-time solvable. Practical methods include dynamic programming for limited resources, label-setting algorithms, Lagrangian relaxation, and approximation schemes.

8. Algorithm Engineering and Implementation

Data Structures

Use adjacency lists for sparse graphs and adjacency matrices for dense graphs or constant-time lookup. In flow implementations, store each directed edge together with its reverse edge. Updating both residual capacities must be atomic from the algorithm’s perspective.

Numerical Issues

Capacities and costs may exceed 32-bit integer ranges. Use sufficiently wide integer types. With floating-point capacities, comparisons to zero can be unstable; an explicit tolerance may be required, although tolerance rules must not invalidate feasibility. If costs are decimals representing money, fixed-point integer units such as cents are usually safer.

Input Validation

Applications should validate that capacities are non-negative, endpoints exist, source and sink are distinct, and demand totals are consistent. Negative-cost cycles in a residual network require careful handling because they may permit cost improvement without changing total flow.

Choosing an Algorithm

Correctness and scalability must be evaluated together. An asymptotically efficient method may perform poorly because of memory locality, priority-queue overhead, or excessive object allocation.

9. AI and Machine-Learning Applications

Network algorithms are important in AI because many learning and inference tasks can be expressed through structured relationships.

Computer vision. Image segmentation can use graph cuts. Pixels or superpixels become vertices, neighboring relationships become edges, and capacities encode similarity and boundary penalties. An s–t cut separates foreground from background under an energy model.

Object tracking. Detections in consecutive frames can be connected in a graph. Edge costs measure appearance and motion incompatibility. Minimum-cost flow can select temporally consistent tracks.

Knowledge graphs. Shortest paths support relation discovery, explanation, and constrained reasoning. However, a shortest path is only meaningful if edge weights reflect a defensible semantic cost.

Neural computation and systems. Directed acyclic graphs represent computational dependencies. Critical-path analysis identifies the longest-latency chain, while resource-aware scheduling may use matching or flow formulations.

Recommendation and assignment. Bipartite matching can assign users to content, jobs to workers, or experts to tasks while enforcing capacity and fairness constraints.

Algorithmic results should not be mistaken for neutral decisions. The graph structure, weights, capacities, and constraints encode design choices and possibly historical bias.

10. Illustrative Case Study: Emergency Medical Supply Routing

Background

Consider a regional health authority distributing vaccines from two storage centers to four clinics. Roads have travel costs and daily capacity limits. The authority must deliver a fixed quantity while minimizing transportation cost and ensuring that no road is overloaded.

Problem

Each storage center supplies a number of doses, and each clinic has a demand. Direct shipment is not always possible. The network contains shared roads, so independently choosing the cheapest route for each clinic could exceed capacity.

Analysis

A maximum-flow model first tests whether total demand is feasible. Source-to-warehouse capacities represent available doses, warehouse-to-clinic or transshipment edges represent roads, and clinic-to-sink capacities represent demand. If maximum flow is less than total demand, the minimum cut identifies the bottleneck—perhaps a bridge, warehouse, or final-mile road.

If all demand is feasible, assign a cost to each road and solve a minimum-cost-flow problem. The resulting flow specifies how many doses should travel on each route. If a clinic requires priority treatment, this can be represented through demand constraints or carefully justified penalty costs, rather than by silently changing capacities.

Approach and Solution

1. Create a directed network with source, warehouses, roads, clinics, and sink.
2. Set integer capacities in dose units.
3. Run maximum flow to test feasibility.
4. If feasible, add transportation costs and solve minimum-cost flow.
5. Inspect the residual network and binding constraints.
6. Perform sensitivity analysis by increasing the capacity of candidate bottlenecks.

Outcome

The authority obtains a feasible allocation and a quantified minimum transportation cost. The cut structure reveals which road improvements would create the greatest additional delivery capacity. Scenario analysis can then test road closures, uncertain demand, or cold-chain restrictions.

Learning Points

The case demonstrates that routing, capacity allocation, and cost minimization are distinct layers. A route that is individually cheapest may be globally harmful. The residual network supports revision when conditions change, and the minimum cut provides an interpretable explanation of system limitations. In practice, uncertainty, travel-time variability, equity, and medical safety requirements must be incorporated beyond the basic deterministic model.

11. Limitations, Governance, and Contemporary Developments

Network models simplify reality. Capacities may be uncertain, travel costs may change over time, and demand may be stochastic. A deterministic optimum can be fragile under disruption. Robust optimization protects against specified uncertainty sets, while stochastic programming models scenarios and probabilities. Online and dynamic algorithms update routes as information arrives.

Fairness is a governance concern in allocation networks. A flow that maximizes throughput may systematically underserve remote communities. Constraints for minimum service levels, proportional allocation, or priority groups can make the objective more socially defensible, although they may increase cost.

Privacy also matters when graph edges encode individuals, transactions, or relationships. Access control, aggregation, anonymization, and differential-privacy techniques may be required. In AI systems, graph optimization should be auditable: stakeholders should understand the objective, constraints, data sources, and reasons for bottleneck decisions.

Recent research combines classical network optimization with machine learning. Learned heuristics predict promising branching decisions, estimate edge costs, or guide routing, while exact optimization verifies feasibility. Differentiable optimization layers attempt to integrate optimization into neural networks, but issues of stability, constraint satisfaction, distribution shift, and explainability remain active research topics.

Best Practices

1. Define vertices, edges, direction, weights, capacities, and units explicitly.
2. Match the algorithm to edge-weight assumptions and graph density.
3. Check feasibility before optimizing cost.
4. Preserve reverse residual edges correctly in flow implementations.
5. Use integer scaling for monetary and discrete quantities where possible.
6. Validate solutions using conservation, capacity, and objective checks.
7. Report bottlenecks and sensitivity, not only the optimal objective value.
8. Test on disconnected graphs, zero-capacity edges, parallel edges, and extreme values.
9. Consider uncertainty, fairness, privacy, and operational constraints.
10. Distinguish a mathematically optimal model solution from a deployable policy.

Chapter Summary

Paths and flows provide a unified language for routing, allocation, communication, logistics, and structured AI problems. Shortest-path algorithms optimize additive path weights: Dijkstra’s algorithm requires non-negative weights, Bellman–Ford handles negative edges and detects reachable negative cycles, and Floyd–Warshall solves all-pairs problems in cubic time. Flow networks add capacities and conservation constraints. Residual networks permit revisions through reverse edges, while augmenting paths increase flow. The max-flow min-cut theorem establishes both optimality and a practical interpretation of bottlenecks.

Minimum-cost flow extends maximum flow by incorporating per-unit costs. Bipartite matching can be reduced to flow, while minimum spanning trees, multi-commodity flow, and constrained shortest paths address different network objectives. Algorithm selection depends on graph structure, numerical assumptions, scale, and required guarantees. In AI applications, network models support segmentation, tracking, assignment, knowledge reasoning, and resource scheduling. Responsible practice requires attention to uncertainty, fairness, privacy, explainability, and the consequences of encoded modeling choices.

Key Terms

Graph: A structure consisting of vertices and edges.

Directed graph: A graph whose edges have orientation.

Weighted graph: A graph whose edges carry numerical values.

Path: A sequence of connected vertices.

Shortest path: A minimum-weight path between specified vertices.

Relaxation: An operation that improves a distance estimate when a better route is found.

Residual network: A network representing remaining and reversible flow capacity.

Capacity: The maximum flow permitted on an edge.

Flow conservation: Equality of inflow and outflow at intermediate vertices.

Augmenting path: A source-to-sink path in a residual network.

Maximum flow: A feasible flow of greatest value.

Cut: A partition separating source and sink.

Minimum cut: A source–sink cut with least capacity.

Minimum-cost flow: A feasible flow minimizing total edge cost.

Bipartite matching: A set of non-overlapping edges between two vertex sets.

Minimum spanning tree: A least-weight tree connecting all vertices of an undirected graph.

Negative cycle: A cycle whose total edge weight is negative.

Multi-commodity flow: Simultaneous flows for multiple demands sharing capacities.

Residual capacity: Capacity available for additional or reversed flow.

Reduced cost: A reweighted edge cost based on vertex potentials.

Review Questions

Short Answer Questions

1. Why does Dijkstra’s algorithm require non-negative edge weights?
2. Define flow conservation in a capacitated network.
3. What information does a residual edge represent?
4. State the max-flow min-cut theorem.
5. How can bipartite matching be transformed into a flow problem?

Long Answer Questions

1. Explain Dijkstra’s and Bellman–Ford algorithms, including their assumptions, correctness intuition, and time complexities.
2. Describe the Ford–Fulkerson method and explain how reverse residual edges can improve an earlier routing decision.
3. Derive the Floyd–Warshall recurrence and discuss when it is preferable to repeated single-source shortest-path algorithms.
4. Explain minimum-cost flow and the role of reduced costs and vertex potentials.
5. Compare shortest paths, maximum flow, minimum spanning trees, and multi-commodity flow in terms of objectives and constraints.

Analytical / Application Questions

1. Design a flow network for assigning instructors to courses when each instructor has a teaching limit and each course has one required instructor. Explain how feasibility and fairness constraints could be represented.
2. A transport network has adequate total road capacity but cannot satisfy all regional demand after one bridge closes. Explain how maximum flow and the minimum cut can diagnose the cause and guide investment.
3. Propose an AI-enabled routing system for emergency supplies. Identify the graph model, objective function, uncertainty issues, ethical risks, and validation tests required before deployment.

Multiple Choice Questions with Answers

Question 1

Which condition is required for Dijkstra’s algorithm to be correct?

A. All edge weights must be equal

B. All edge weights must be non-negative

C. The graph must be acyclic

D. Every vertex must be reachable from the source

Correct Answer: B. All edge weights must be non-negative

Question 2

What does relaxation do in a shortest-path algorithm?

A. Deletes an edge with the greatest weight

B. Tests whether a route through one vertex improves a distance estimate

C. Converts a directed graph into an undirected graph

D. Finds a minimum cut

Correct Answer: B. Tests whether a route through one vertex improves a distance estimate

Question 3

The general time complexity of Bellman–Ford using adjacency-list edge scans is:

A. O(nm)

B. O(n²)

C. O(m log n)

D. O(2ⁿ)

Correct Answer: A. O(nm)

Question 4

A feasible flow must satisfy which condition at every intermediate vertex?

A. Outflow is always zero

B. Inflow equals outflow

C. Inflow must exceed capacity

D. All incident edges must be saturated

Correct Answer: B. Inflow equals outflow

Question 5

A residual reverse edge in a flow network represents:

A. A permanently forbidden direction

B. The ability to cancel previously assigned flow

C. An edge with double capacity

D. A shortest path tree edge

Correct Answer: B. The ability to cancel previously assigned flow

Question 6

According to the max-flow min-cut theorem, the maximum flow value equals the:

A. Number of vertices in the network

B. Total capacity of all edges

C. Capacity of the minimum source–sink cut

D. Length of the longest path

Correct Answer: C. Capacity of the minimum source–sink cut

Question 7

In a flow reduction of bipartite matching, the capacity of each source-to-left-part vertex edge is usually:

A. 0

B. 1

C. The degree of the vertex

D. Infinity only when the graph is dense

Correct Answer: B. 1

Question 8

Which algorithm is designed to compute shortest paths between all pairs of vertices in a graph with moderate size?

A. Floyd–Warshall

B. Kruskal

C. Hopcroft–Karp

D. Ford–Fulkerson

Correct Answer: A. Floyd–Warshall

Question 9

If an edge carries 5 units of flow and has per-unit cost 3, what is its contribution to total flow cost?

A. 2

B. 8

C. 15

D. 25

Correct Answer: C. 15

Question 10

What does a minimum cut identify in a capacity-constrained network?

A. A set of vertices with maximum degree

B. A bottleneck separating the source from the sink

C. The shortest simple cycle

D. The least expensive spanning tree

Correct Answer: B. A bottleneck separating the source from the sink