Discovering shortest routes between Soviet railroad stations

History

*The reader must have familiarity with Max-Flow algorithms.

Max-Flow algorithms were used in the Soviet Union(the green region below) to determine the less cost effective way of carrying goods to Eastern Europian countries.

Carriage of 163000 tons would be done from the Soviet to the Eastern European countries; the paths might be observed in the following map:

Min-Cut approach was used in order to determine where the US airplanes could intervene -- essentially the regions of train rails that has the maximum flow going through them. Such a region is outlined above by the encircled black region named as "The Bottleneck.".

Ford-Fulkerson -- in describing their algorithm -- references a report that was written for the US Air Force in 1955 for this purpose.

A different way of finding a maximum flow other than the algorithm developed by Ford and Fulkerson is called Dinic's algorithm:

Essentially, build a level graph where there is at most one edge between each vertices.

- Here is an example level graph with flow capacities:

- Find an augmenting path:

- Then find a bottleneck:

- Then, find an augmenting path from the bottleneck to the sink and increase the flow:

- Repeat the process for other vertices until no augmenting path could be found:

- An example with more nodes -- image order is left to right:

- Drawing a level graph would take O(E) time and constructing a blocking flow would take O(VE) time. The running time is O(VE^2).

* Chih-Hsuan Kuo's presentation is used as a reference.