<p>What you're describing, where you minimize the sum of $f(u,v)w(u,v)$ with a given flow value $|f|$ isn't, in fact, the max-flow problem—it's the <a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem" rel="nofollow">min-cost flow problem</a>. If you constrain the flow value to be 1, and all capacities are set to 1, it's pretty clear that this problem is equivalent to finding the shortest path.</p>

<p>Basically, unit-capacity flow problems find edge-disjoint paths. If you set the flow value to be 1, you'll find only a single path. If you're working with min-cost flow, that path will necessarily be the shortest path (and, therefore, the cheapest flow).</p>

<p>If this is <em>not</em> what the book is asking, and it's really asking you about max-flow, I suspect there must be some details missing from your description. (For example, you could easily have a single node $t&#39;$ before $t$, with $c(t&#39;,t)=1$, so max-flow would have a flow value of 1, yielding a single path; however, that would still ignore the edge costs, and would just find any path, <em>unless</em> you're specifically using the Edmonds-Karp algorithm, which uses BFS to find its augmenting paths; in that case, you would, at least, find the shortest <em>unweighted</em> path.)</p>

CC BY-SA 3.0
2011-06-25T15:00:48.567Z
2011-06-25T15:07:53.057Z
2011-06-25T15:07:53.057Z
Magnus Lie Hetland
<p>Shortest path costs $O(E)$ using breadth-first search
The best algorithms for max-flow are something like $O(EV)$ (plus some logarithmic factors).</p>

<p>So I do not know in what sense they are equivalent (other than they are both polynomial time)</p>

CC BY-SA 3.0
2011-06-25T13:50:13.063Z
That's what i've thought and i decided to ask here. I am really confused of what to do.
brandon Wright
CC BY-SA 3.0
2011-06-25T15:02:00.953Z
The shortest paths he's talking about are weighted, so BFS is probably not relevant.
Magnus Lie Hetland
CC BY-SA 3.0
2011-06-25T13:36:21.323Z
2011-06-25T13:36:21.323Z
David Harris
<p>Actually finding the min-cut from s to t (whose cut has the minimum capacity cut) is equivalent with finding a max flow f from s to t.</p>

<p>There are different ways to find the augmenting path in Ford-Fulkerson method and one of them is using of shortest path, therefore, I think the mentioned expression was something like above.</p>

<p>Some other ways to choose augmenting path:</p>

<p>1 - Fattest path : Implemented by using priority queue.</p>

<p>2 - DFS path : Implemented by using stack(DFS).</p>

<p>3 - Random path : Implemented by randomized queue.</p>

<p><a href="https://www.coursera.org/learn/algorithms-part2/lecture/xmDao/running-time-analysis" rel="nofollow noreferrer">https://www.coursera.org/learn/algorithms-part2/lecture/xmDao/running-time-analysis</a></p>

CC BY-SA 4.0
2018-06-14T17:33:38.883Z
The question doesn't say anything about min-cuts so I don't see how this answers the question.
D.W.
CC BY-SA 4.0
2018-06-16T11:49:11.640Z
Dear @D.W. I was just saying, maybe the mentioned expression was something about relationship between max-flow and min-cuts not max-flow and shortest path or something about choices for finding augmenting path.
Mohammad Moridi
CC BY-SA 4.0
2018-06-14T11:29:55.957Z
2018-06-14T11:29:55.957Z
Mohammad Moridi
<p>I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book.</p>

<p>We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ where weight of every edge $(u,v) \in E$ is a positive number ($w(u,v)>0$).</p>

<p>Actually it asks to prove that finding the shortest path from $s$ to $t$ is equivalent with finding a max flow $f$ from $s$ to $t$.</p>

<p>$f$ minimizes the amount of $Σ_{(u,v)\in E} f(u,v)w(u,v)$ and has the value of $|f|=1$.</p>

<p>It seems that i am missing something. Can anyone help me with this cause i really hate leaving unsolved exercises when reading a book.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2011-06-25T15:03:26.647Z
Which book (and which exercise) is this?
Magnus Lie Hetland
CC BY-SA 3.0
2011-06-25T16:29:59.647Z
Seems to be off-topic here, voted to close.
Jukka Suomela
<graph-algorithms><linear-programming><max-flow>
shortest path & max flow
brandon Wright
# shortest path & max flow

(Asked by: username_0 on 2011-06-25)

I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book.

We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ where weight of every edge $(u,v) \in E$ is a positive number ($w(u,v)>0$).

Actually it asks to prove that finding the shortest path from $s$ to $t$ is equivalent with finding a max flow $f$ from $s$ to $t$.

$f$ minimizes the amount of $Σ\_{(u,v)\in E} f(u,v)w(u,v)$ and has the value of $|f|=1$.

It seems that i am missing something. Can anyone help me with this cause i really hate leaving unsolved exercises when reading a book.

Thanks.

**Tags:** graph-algorithms, linear-programming, max-flow

> **Comments:**
> **username_1**: Which book (and which exercise) is this?  
> **username_2**: Seems to be off-topic here, voted to close.  

---

## 3 answers

### Answer by username_1 on 2011-06-25. Score: 4

What you're describing, where you minimize the sum of $f(u,v)w(u,v)$ with a given flow value $|f|$ isn't, in fact, the max-flow problem—it's the [min-cost flow problem](http://en.wikipedia.org/wiki/Minimum-cost_flow_problem). If you constrain the flow value to be 1, and all capacities are set to 1, it's pretty clear that this problem is equivalent to finding the shortest path.

Basically, unit-capacity flow problems find edge-disjoint paths. If you set the flow value to be 1, you'll find only a single path. If you're working with min-cost flow, that path will necessarily be the shortest path (and, therefore, the cheapest flow).

If this is *not* what the book is asking, and it's really asking you about max-flow, I suspect there must be some details missing from your description. (For example, you could easily have a single node $t'$ before $t$, with $c(t',t)=1$, so max-flow would have a flow value of 1, yielding a single path; however, that would still ignore the edge costs, and would just find any path, *unless* you're specifically using the Edmonds-Karp algorithm, which uses BFS to find its augmenting paths; in that case, you would, at least, find the shortest *unweighted* path.)


---

### Answer by username_3 on 2011-06-25. Score: 1

Shortest path costs $O(E)$ using breadth-first search
The best algorithms for max-flow are something like $O(EV)$ (plus some logarithmic factors).

So I do not know in what sense they are equivalent (other than they are both polynomial time)

> **Comments:**
> **username_0**: That's what i've thought and i decided to ask here. I am really confused of what to do.  
> **username_1**: The shortest paths he's talking about are weighted, so BFS is probably not relevant.  

---

### Answer by username_4 on 2018-06-14. Score: -1

Actually finding the min-cut from s to t (whose cut has the minimum capacity cut) is equivalent with finding a max flow f from s to t.

There are different ways to find the augmenting path in Ford-Fulkerson method and one of them is using of shortest path, therefore, I think the mentioned expression was something like above.

Some other ways to choose augmenting path:

1 - Fattest path : Implemented by using priority queue.

2 - DFS path : Implemented by using stack(DFS).

3 - Random path : Implemented by randomized queue.

<https://www.coursera.org/learn/algorithms-part2/lecture/xmDao/running-time-analysis>

> **Comments:**
> **username_5**: The question doesn't say anything about min-cuts so I don't see how this answers the question.  
> **username_4**: Dear @username_5 I was just saying, maybe the mentioned expression was something about relationship between max-flow and min-cuts not max-flow and shortest path or something about choices for finding augmenting path.  

---

