Network Flow and Routing

Network Flow and Routing

Network Flow and Routing: Shortest Paths, Maximum Flow, Minimum-Cost Flow, Spanning Trees, Travelling Salesman and Postman Routes

Networks and the problems on them

A network is a set of nodes joined by arcs. Each arc may carry a cost (a length, a time, a price per unit) and a capacity (the most that can pass along it). The tool reads the network as one arc per line, "from, to, cost, capacity", with any words or numbers as node names, and treats the arcs as directed (from the first node to the second) or undirected (usable either way) as the radio says; a spanning tree, a tour and a postman route always use the arcs as undirected edges. Optional coordinates place the nodes in the drawing and, for the travelling salesman, define Euclidean distances. The problems solved are the classical ones of operations research: the cheapest route between two nodes, the cheapest routes between all pairs, the most that can be shipped from a source to a sink, the cheapest way to ship given amounts from supply nodes to demand nodes, the cheapest set of edges joining every node, the shortest round trip through every node, and the shortest closed walk along every edge. Every one of them is a linear program (the transportation and assignment problems of the companion tool are special cases of the minimum-cost flow), but each has a combinatorial algorithm that is faster and, printed step by step, more instructive.

Shortest path: Dijkstra's labelling

With non-negative arc costs Dijkstra's method (1959) finds the shortest path from a source to every node. Each node carries a tentative label d, the length of the best path found so far (∞ until a path is found), and a predecessor. At each step the unsettled node with the smallest label is settled: its label is final, because any other route to it would leave the settled set through a node whose label is at least as large and could only grow from there, costs being non-negative. Each arc (u, v) out of the settled node is then relaxed, d(v) ← min(d(v), d(u) + c(u, v)), recording u as the predecessor when the label improves. The tool prints the label table after every step (bold = improved, grey = settled) and reads the path backwards through the predecessors. A subpath of a shortest path is itself shortest, so the predecessors form the shortest-path tree from the source and one run gives the distance to every node; the sink only decides when to stop.

Negative costs: Bellman–Ford

A negative arc cost (a credit, a gain) breaks Dijkstra's rule: a settled label may later be lowered through a negative arc. The Bellman–Ford method (Bellman 1958, Ford 1956) instead relaxes every arc in turn and repeats the sweep; after k sweeps every shortest path of at most k arcs has been found, so n − 1 sweeps settle everything when no cycle of negative total cost is reachable. If a further sweep still improves a label, such a cycle exists; the tool extracts it from the predecessor chain and reports it, because a walk through it can be made cheaper by every extra lap and no shortest path exists. An undirected edge of negative length is such a cycle by itself and is refused.

All pairs: Floyd–Warshall

Floyd (1962) and Warshall (1962) compute every shortest distance at once in n³ operations. Starting from the arc costs (∞ where there is no arc, 0 on the diagonal), the nodes are admitted one at a time as intermediate nodes: after node k is admitted, d(i, j) = min(d(i, j), d(i, k) + d(k, j)) is the shortest path that uses only the first k nodes in between. A negative diagonal entry at the end reveals a cycle of negative total cost. The tool prints the matrix, the eccentricity of each node (its distance to the farthest node it can reach) and the diameter.

Maximum flow: Ford–Fulkerson augmenting paths and the minimum cut

A flow assigns to each arc an amount between zero and its capacity such that what enters each intermediate node leaves it; its value is the net amount leaving the source (and arriving at the sink). Ford and Fulkerson (1954) proved the maximal-flow minimal-cut theorem: the largest value of any flow equals the smallest capacity of any cut, a cut being a set of arcs whose removal separates the source from the sink (counting only the arcs that cross it from the source side to the sink side). Any cut bounds any flow, since every unit must cross it, so a flow and a cut of equal value prove each other optimal. The constructive method is the augmenting path: in the residual network every arc offers the room left (capacity − flow) in its direction and the flow already placed as a backward arc (so that flow can be cancelled); any source-to-sink path in it raises the flow by its bottleneck, the smallest residual capacity along it. When no augmenting path remains, the nodes still reachable from the source form the source side S of a cut every arc of which is saturated, which is the proof. Edmonds and Karp (1972) choose the augmenting path with the fewest arcs (breadth-first search), which guarantees at most n·m/2 augmentations for any capacities; the tool lists each path with its bottleneck, the flow on every arc, the cut sets S and T and the cut arcs. For an undirected network each edge may carry up to its capacity in either direction. A path of unlimited capacity makes the flow unbounded and is reported.

The theorem holds for one commodity. Ford and Fulkerson's memorandum points out (p. 7) that with several sources each restricted to its own sink it fails: in a three-arm star of capacity 2 per arm with three commodities, each from one leaf to another, the smallest set of arcs meeting every chain has value 4 while the largest multicommodity flow is only 3. The tool solves single-commodity problems; a multicommodity problem is a linear program for the Linear Programming tool.

Minimum-cost flow: successive shortest paths with potentials

Each node has a supply b (positive), a demand (negative b) or neither (a transshipment node); supplies and demands must balance. A feasible flow respects the capacities and gives every node a net outflow equal to its b; the problem is to find the cheapest one, cost being Σ c(u, v) f(u, v). The successive-shortest-path method starts from zero flow, which is the cheapest flow of value zero, and repeatedly augments along the cheapest path in the residual network from a node with supply left to a node with demand left, by as much as the supply, the demand and the bottleneck allow; the flow stays the cheapest for the amount sent so far, so the final flow is optimal. Backward residual arcs carry negative costs (undoing a unit refunds its cost), which Dijkstra cannot handle directly; node potentials π are therefore kept such that every residual arc's reduced cost c(u, v) + π(u) − π(v) is non-negative, Dijkstra runs on the reduced costs, and after each path the potentials are increased by the distances found, which keeps the reduced costs non-negative for the next round (nodes not reached are moved by the largest distance). With a negative original cost the first potentials come from one Bellman–Ford pass; a cycle of negative cost in the empty residual network is refused, since the method would need it cancelled first.

The optimality condition printed at the end is that no residual arc with room left has a negative reduced cost (there is then no cycle of negative cost to add to the flow). An arc carrying flow strictly between zero and its capacity has reduced cost zero; a saturated arc may have a negative one (more would be cheaper but there is no room) and an unused arc a positive one. The potentials are the dual prices up to a constant: π(v) − π(u) is the marginal cost of delivering one more unit from u to v through the present flow. The tool's minimum-cost flows are checked against the Linear Programming tool's simplex and against scipy's linear-programming solver on the same arcs, which is how a reader can verify any case: one variable per arc, one balance equation per node, bounds 0 to capacity.

Minimum spanning tree: Kruskal and Prim

A spanning tree joins all n nodes with n − 1 edges and no cycle, and the minimum spanning tree has the least total length (a network of cables, pipes or roads that connects every site). Both classical methods rest on the cut property: the cheapest edge leaving any set of nodes belongs to some minimum spanning tree. Kruskal (1956) scans the edges in order of increasing length and accepts each one that joins two different components, rejecting any that would close a cycle; the tool prints the sorted list with the decision for each edge, using a union-find structure to tell the components apart. Prim (1957; Jarník 1930) grows one tree from a root, adding at every step the cheapest edge between the tree and a node outside it. The two totals agree, and the trees are the same unless lengths tie. A disconnected graph gets a spanning forest from Kruskal and only the root's component from Prim; the tool says so.

Travelling salesman: heuristics, an exact method and a bound

A tour visits every city once and returns to the start; the symmetric travelling-salesman problem asks for the shortest. With n cities there are (n − 1)!/2 distinct tours, so enumeration stops being possible around a dozen cities, and the problem has no known polynomial algorithm. The tool's distances are Euclidean when every city has coordinates, otherwise the entered lengths (every pair must be present). It runs two constructive heuristics from the start city, nearest neighbour (always go to the nearest unvisited city) and cheapest insertion (grow a sub-tour by inserting the city whose cheapest insertion between two consecutive tour cities adds the least), improves each by 2-opt (Croes 1958: replace two tour edges (a, b), (c, d) by (a, c), (b, d), which reverses the segment between them, whenever that shortens the tour, until no such move remains), and for up to 60 cities repeats nearest neighbour plus 2-opt from every city and keeps the best. For 12 cities or fewer it also solves the problem exactly by the Held–Karp dynamic programme (1962): C(S, j), the shortest path from the start through the set S of cities ending at j, is built up over the 2ⁿ⁻¹ subsets, and the best C(all, j) + d(j, start) is the optimum.

To know how good a heuristic tour is when the exact method is out of reach, the tool computes the lower bound of Held and Karp (1970, 1971). A 1-tree is a minimum spanning tree on the cities other than the start together with the two cheapest edges at the start; every tour is a 1-tree (a tour minus the start's two edges is a path, which is a spanning tree), so the minimum 1-tree can be no longer than the optimal tour. The bound is sharpened by node weights π: with every edge costing d(i, j) + π(i) + π(j), a tour's length changes by exactly 2 Σπ because every city has degree 2, so L(π) = (minimum weighted 1-tree) − 2 Σπ is a lower bound for every π, and it is raised by subgradient ascent, π(i) ← π(i) + t (degree of i in the 1-tree − 2), which penalizes the cities the 1-tree visits too often. On the 42-city instance of Dantzig, Fulkerson and Johnson (1954), the first large problem ever solved to optimality (by hand, with cutting planes), the tool's bound reaches 696.98 and the multi-start 2-opt reaches the published optimum 699, so the two bracket the answer within 0.3 %. The gap printed is (best tour − bound)/bound, an upper bound on how far the tour can be from the optimum.

Chinese postman: odd nodes, matching and the Euler circuit

A postman, a street sweeper or an inspection vehicle must traverse every edge of a street network at least once and return to the start by the shortest closed walk (Kwan 1962; Edmonds and Johnson 1973). Euler (1736) showed that a closed walk using every edge exactly once exists if and only if every node has an even number of edges; such a walk is then found by Hierholzer's method (1873), which follows unused edges until it returns to the start and splices in the detours it skipped. When some nodes have odd degree, always an even number of them, some edges must be traversed twice: the odd nodes are paired off and the shortest path between the two nodes of each pair is walked a second time, which makes every degree even, and the pairing of least total length is the one to choose. For up to 12 odd nodes the tool enumerates every perfect matching ((k − 1)!! of them: 1, 3, 15, 105, 945, 10,395) with the shortest-path distances between odd nodes; a street network with more odd nodes needs Edmonds's blossom algorithm, which the tool does not implement. The route length is the sum of all edge lengths plus the matching, and the route itself is printed leg by leg with the second traversals marked.

Drawing

The network is drawn with GD at the pasted coordinates, or, without them, at a spring layout (Fruchterman and Reingold 1991: nodes repel, edges pull, the positions settle), in which only the connections carry meaning. A tour without coordinates is drawn on a map reconstructed from the distances by classical multidimensional scaling (the two leading eigenvectors of the double-centred squared-distance matrix), which reproduces planar distances exactly and gives a sensible map for road distances. Parallel and opposite arcs are bent apart; the solution is drawn in red, the source in green and the sink in orange, the cut sides shaded, the odd-degree nodes in yellow.

Limits and conventions

Up to 80 nodes and 900 arcs; costs may be negative only for the shortest-path problems (Bellman–Ford, Floyd–Warshall) and, without a negative cycle, the minimum-cost flow; capacities are non-negative, "inf" for unlimited; a self-loop is ignored and parallel arcs are kept (their capacities add in a flow problem, the cheaper one is used by a path). The exact tour is computed for 12 cities or fewer, the multi-start heuristic for 60 or fewer, the postman matching for 12 odd nodes or fewer. Node names are matched exactly, then numerically (7 = 7.0), then without regard to case. The tool prints no units: costs, lengths and capacities are whatever the analyst entered, consistently.