Tools › Operations Research › Networks and Routing › Network Flow and Routing › Example

Nine-node network: Dijkstra's label table, Edmonds–Karp augmenting paths and the minimum cut

Tool	Network Flow and Routing
Source	Ford, L. R., and Fulkerson, D. R. (1954). Maximal Flow Through a Network. Research Memorandum RM-1400, The RAND Corporation, Santa Monica, CA (the maximal-flow minimal-cut theorem); Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, Vol. 1, No. 1, pp. 269–271; Edmonds, J., and Karp, R. M. (1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." Journal of the ACM, Vol. 19, No. 2, pp. 248–264.
Level	Undergraduate

Problem

A directed network of 9 nodes and 14 arcs, each with a cost (length) and a capacity, joins a source (node 1) to a sink (node 9). Find the shortest path from 1 to 9 by Dijkstra's labelling, showing the label of every node after each step, and the maximum flow from 1 to 9 by augmenting paths, with the minimum cut that proves it optimal.

Inputs to Enter

Arcs (from, to, cost, capacity): 1-2 4/12, 1-4 2/11, 2-3 3/5, 2-4 1/3, 2-5 5/6, 3-6 2/9, 4-5 1/7, 4-7 6/5, 5-6 4/4, 5-8 3/8, 6-8 1/2, 6-9 5/10, 7-8 2/6, 8-9 2/9; directed; source 1, sink 9
Problem: shortest path and maximum flow (the default); coordinates given for the drawing

Open the Network Flow and Routing tool (loaded with this example)

Answers

Dijkstra settles the nodes in the order 1 (0), 4 (2), 5 (3), 2 (4), 8 (6), 3 (7), 6 (7), 7 (8), 9 (8); shortest path 1 → 4 → 5 → 8 → 9 of length 8; distances 0, 4, 7, 2, 3, 7, 8, 6, 8 to nodes 1 … 9
Edmonds–Karp augmenting paths: 1-2-3-6-9 (5), 1-2-5-6-9 (4), 1-2-5-8-9 (2), 1-4-5-8-9 (6), 1-4-7-8-9 (1); maximum flow 18
Minimum cut S = {1, 2, 4, 5, 7, 8}, T = {3, 6, 9}: arcs 2→3 (5), 5→6 (4), 8→9 (9), capacity 18 = the flow (Ford–Fulkerson theorem)
The same network as undirected edges: shortest path 8, maximum flow 19; minimum-cost flow of 15 units from 1 to 9 costs 166 (lp_lib and scipy linprog agree); minimum spanning tree 14; the undirected network is Eulerian (postman route 41)

Notes

The tool's default inputs are this network; press Submit. The network is the tool's own illustrative case (no printed worked example has it); every number is reproduced by scipy.sparse.csgraph (dijkstra, maximum_flow, minimum_spanning_tree) and scipy.optimize.linprog in References/Network-Flow/checks/ (test_network_flow_routing.php, 558 checks, which also reproduce the three-commodity counterexample of RM-1400 p. 7 and bracket the published optimum 699 of the Dantzig–Fulkerson–Johnson 42-city instance between the tool's multi-start 2-opt tour, 699, and its Held–Karp bound, 696.98).