Alexrider726's blog

How to solve this?
By Alexrider726, history, 17 months ago, In English

Given the capacities of edges in a directed graph, find the maximum amount of flow that you can pass through a single path from the source to the sink, for every possible choice of source and sink vertices.Can anyone give me an idea of how to approach this question using Floyd-Warshall algorithm. I am very curious after reading https://codeforces.net/blog/entry/117814

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Alexrider726 (previous revision, new revision, compare).

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Change the signs of all capacities. This is not a necessary step, but it makes what I am about to explain more straightforward.

Floyd-Warshall gives you for each pair of 2 vertices the best distance between them. In this problem, distance is defined as the maximal weight of an edge that we passed through. Keeping this in mind, we can just run the normal Floyd-Warshall to find the minimal distance, but instead of the distance being $$$d1+d2$$$, it will be $$$max(d1,d2)$$$.

Time complexity is $$$O(N^3)$$$. If instead of Floyd-Warshall we use Dijkstra, the time complexity becomes $$$O(N M log N)$$$, where $$$M$$$ is the number of edges.

However, this problem can also be solved in $$$O(N^2 + M \alpha (N))$$$.

Assume that weights are still inverted.

We will observe that there always exists an optimal path that goes only through the edges of MST (Minimum spanning tree). Therefore we will find the spanning tree of the graph. Now the optimal path between 2 vertices will be their unique path on the MST. We can find the lengths of those paths by running DFS from each vertex.

→ Reply