Sending maximum flow along the least-cost path in Successive shortest path algorithm?

Revision en1, by mohamedeltair, 2019-07-11 06:56:15

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)?

Tags #mincost flow


  Rev. Lang. By When Δ Comment
en1 English mohamedeltair 2019-07-11 06:56:15 774 Initial revision (published)