1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Which book (and which exercise) is this? $\endgroup$
    – Magnus Lie Hetland
    Jun 25, 2011 at 15:03
  • 2
    $\begingroup$ Seems to be off-topic here, voted to close. $\endgroup$
    – Jukka Suomela
    Jun 25, 2011 at 16:29

3 Answers 3

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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)

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's what i've thought and i decided to ask here. I am really confused of what to do. $\endgroup$
    – brandon Wright
    Jun 25, 2011 at 13:50
  • $\begingroup$ The shortest paths he's talking about are weighted, so BFS is probably not relevant. $\endgroup$
    – Magnus Lie Hetland
    Jun 25, 2011 at 15:02
-1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The question doesn't say anything about min-cuts so I don't see how this answers the question. $\endgroup$
    – D.W.
    Jun 14, 2018 at 17:33
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Moridi
    Jun 16, 2018 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.