Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

mohamedeltair's blog

By mohamedeltair, history, 3 months ago, In English,

In Successive shortest path algorithm in every iteration, we find the path that has the minimum cost (if we considered sending a unit of flow along it), and then we send along this path the maximum flow that we can.

My question is, why is it correct to send the maximum flow that we can along the found least-cost path? Imagine a scenario where we found the least-cost path, then sent a unit flow along it. This may lead to new paths appearing (via edges through which we couldn't send a flow before but now we can). Can't a one of these new paths be the new least-cost path, and hence we should have sent the next unit of flow along it (not along the previously found least-cost path)?

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
3 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

The invariant the algorithm tries to hold is not necessarily that flow is pushed through the current shortest path, but rather the negative cost cycle condition: a feasible flow is optimal iff its transportation network contains no negative cost cycle.

Initially, by hypothesis, there is no negative cost cycle. Suppose we form one by updating the network following the augmentation of the shortest path $$$P$$$. This means that the reversal of some edge $$$(u, v)$$$ along the shortest path formed a negative cycle $$$W$$$. This contradicts that $$$P$$$ was the shortest path, as we could have chosen the path from the source to $$$u$$$, then went along the edges of W, then from $$$v$$$ to the destination.

There are no capacities involved in this proof, as long as the feasible flow conditions are satisfied; and this happens regardless if we update with 1 unity or the most we could.

Another misconception the community has is regarding the algorithm's time complexity. I have seen several editorials mention its time complexity as $$$O(VE \cdot T(V, E))$$$, where $$$T(V, E)$$$ is the time to solve the shortest path problem, but this is wrong. This algorithm does not run in polynomial time. In this form, its time complexity is in fact $$$O(VU \cdot T(V, E))$$$, where $$$U$$$ is the maximum capacity. You can see in the min25 blog an idea of such a test.

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks for your comment.

    From your comment, what I got is:

    The algorithm tries to ensure no negative cycles are introduced after every path augmentation, and augmenting the shortest path ensures so. But still this leads us to the starting point, we need to push the flow in the current shortest path to ensure no negative cycles are introduced.

    So, consider the case when we push the most we can in the current shortest path $$$p$$$ (let these be $$$x$$$ flow units). If we pushed one unit of $$$x$$$ at a time through $$$p$$$, there is a possibility that at some time $$$t$$$, $$$p$$$ is not the shortest path anymore. How is it guaranteed that after $$$t$$$ no negative cycles are introduced?

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think I have got it. If after $$$t$$$ a negative cycle is introduced, the part of this cycle external to $$$p$$$ would have been existing from the beginning (when $$$p$$$ was the shortest path), which leads to the contradiction bciobanu talked about.