Transfinite Ford-Fulkerson on a finite network

It is well-known that the Ford-Fulkerson algorithm for finding a maximum flow in a network need not terminate if we allow the arc capacities to take irrational values. Every non-Terminating example converges to a limit flow, but this limit flow need not be a maximum flow. Hence, one may pass to the limit and begin the algorithm again. In this way, we may view the Ford-Fulkerson algorithm as a transfinite algorithm. We analyze the transfinite running-Time of the Ford-Fulkerson algorithm using ordinal numbers, and prove that the worst case running-Time is ω Θ (| E |). An upper bound of ω | E | is established via induction on | E |. For the lower bound, we first show that we can model the Euclidean algorithm via Ford-Fulkerson on a certain network. By running this example on a pair of incommensurable numbers, we obtain a new robust non-Terminating example. We then describe how to carefully glue k copies of our Euclidean example in parallel and describe a run of the Ford-Fulkerson algorithm that requires at least ω Ω (| E |) steps. This run includes an infinite number of recharging steps that reinitialize the k copies of our Euclidean example.