Tools › Operations Research › Networks and Routing

Networks and Routing

Network Flow and Routing

Solves the classical network problems of operations research from a pasted arc list and prints every step the way a textbook works them: the shortest path by Dijkstra's labelling (the label table of every iteration) or by Bellman–Ford when a cost is negative (with negative-cycle detection), all pairs by Floyd–Warshall, the maximum flow by the Edmonds–Karp augmenting paths with the bottleneck of each path and the minimum cut that proves it optimal (Ford and Fulkerson's theorem), the minimum-cost flow by successive shortest paths with node potentials and the reduced-cost optimality check, the minimum spanning tree by Kruskal's sorted-edge scan (accept / reject) and by Prim's growth from a root, the travelling-salesman tour by nearest neighbour, cheapest insertion and 2-opt with the exact Held–Karp dynamic programme for up to 12 cities and the 1-tree / Held–Karp lower bound so that the gap is known, and the Chinese postman route (odd-node matching, Euler circuit) for an undirected street network. The network is drawn with the solution highlighted. The default network (illustrative, 9 nodes, 14 arcs with lengths and capacities) gives the shortest path 1–4–5–8–9 of length 8 and a maximum flow of 18 across the cut {2→3, 5→6, 8→9}; the travelling-salesman examples are the first ten cities and the full 42-city road-distance instance of Dantzig, Fulkerson and Johnson (1954) as distributed in TSPLIB (optimal tour 699).

1 worked example reproduced, listed on the tool page.

Other Operations Research sections

Optimization · Queueing and Simulation · Scheduling · Inventory and Supply Chain · Decision Analysis