# Ford Fulkerson maximum flow for all vertices

Suppose we have a graph $$G(E,V)$$ with a source node $$s$$. Now for any $$t\in V \setminus s$$ I can find the maximum flow from $$s$$ to all possible $$t$$ by using the Ford Fulkerson algorithm $$|V|-1$$ times, once for each $$t$$. I feel like there must be a faster way to compute all $$|V|-1$$ max flows that makes use of dynamic programming techniques. Any ideas?

• Are you trying to get only the maximum among all those flows or do really want to compute every single s-t flow for some fixed s? – Tassle Aug 25 at 15:30
• Thanks for the question. I am interested in every single one, but if there is a an algorithm that only returns the maximum out of all of them I would also be interested. However, I would guess that the maximum flow vertex will almost always be a vertex very close to $s$. – leander Aug 25 at 15:43
• Basically I am trying to rank the nodes with respect to the maximum flow that can reach them. Later on I am planning to select one of them based on a different set of criteria. – leander Aug 25 at 15:44
• For the maximum out of all of them, I think "J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." might be of interest. They provide an algorithm to compute the min cut for a fixed s on the source side with time-complexity O(nm log(n²/m)) (which is the maximum s-t flow for fixed s) (Edit: The time complexity is equal to a single run of Push-Relabel with dynamic trees. I haven't read the paper but you might be able to plug in Ford-Fulkerson instead of Push-Relabel and get the time-complexity of a single FF run) – Tassle Aug 25 at 16:11
• Ah, amazing! That's it! If you post this as an answer I can accept it. Thank you so much. – leander Aug 25 at 16:26

"J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." provides an algorithm to compute the min cut for a fixed s on the source side with time-complexity $$O(nm \log(n^2/m))$$, by reducing the complexity of multiple s-t cuts for varying sinks to the complexity of a single call to the Push-Relabel max-flow algorithm.

This might be adaptable to a version where you can store all the intermediate min-cut values (=max-flow values) for all sinks along the way.