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

Правка en1, от 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)?

Теги #mincost flow

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский mohamedeltair 2019-07-11 06:56:15 774 Initial revision (published)