Network Flow - Minimum flow in a network
-
28-09-2020 - |
質問
I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges.
In a course that I took, the professor told that to find a minimum flow -
1) We need to assign a large capacity to all edges and find flow f
2) Construct G $_{1}$ where all edges are reversed and each edge has capacity f$_{e}$ - l$_{e}$
3) We need to then find the max flow from t to s in G$_{1}$ that is f$_{1}$
4) Then, the minimum flow in G is f-f$_{1}$
My question is- Why can't we find a
s to t
path inG
with the least value of l$_{e}$. The least value of l$_{e}$ would be the minimum flow that could be pushed through the network?
所属していません cs.stackexchange