Consider an undirected weighted graph G with all edges of equal capacity. For each pair of its vertices I need to find the set of paths, which corresponds to max flow of minimal cost between these vertices.
The naive approach is to use some min-cost max-flow algorithm for each pair of vertices, which gives us about o(n^2 * T(min-cost max-flow)). Is there any way to reduce the complexity?
It is also possible to find all min cut (and max-flow) values by constructing Gomory-Hu tree. But I am not sure, if known min cuts can help to reconstruct the corresponding paths.