Talk:Edmonds–Karp algorithm

In the article, it is stated that "The distinguishing feature is that the shortest augmenting path is used at each step, which guarantees that the computation will terminate." However, as I understand it, the use of the shortest augmenting path ensure a faster running time than using breadth-running time. The terminiation of the computation is also ensured in the other algorithms based on Ford-Fulkerson, and has as such nothing to do with the breadth-first search. I will try to work on this entry at a later stage.--Kristjan Wager 09:52, 31 May 2005 (UTC)

The article is precisely correct! Please don't change it without discussion. --Zero 13:42, 31 May 2005 (UTC)

According to Cormen et al's Introduction to Algorithms, 2nd edition, the breadth-first search is done to reduce the search time from $O(E|f^{*}|)$ to $O(VE^{2})$ (see pages 658-663). It has nothing as do with ensuring that the algorithm terminates - this is ensured by the principles of the Ford-Fulkerson method.--Kristjan Wager 14:09, 31 May 2005 (UTC)

No, the $O(E|f^{*}|)$ bound only applies if the capacities are integers. If they are arbitrary real numbers, the Ford-Fulkerson method might fail to terminate and can even converge towards the wrong answer. See Ford-Fulkerson algorithm. --Zero 20:08, 31 May 2005 (UTC)

Ok, thank you for clearifying. While I was aware of the problems with Ford-Fulkerson in regards to real numbers, I was unaware that Edmonds-Karp fixed it. Interesting that Cormen et al didn't mention that aspect. I think I need to read the original article. --Kristjan Wager 07:34, 1 Jun 2005 (UTC)

In the figure: Ek-flow 4.png, there is an arrow upside down, please correct it.

The arrow is drawn correctly. What happens here is that flow is "sent back" from E to D. The flow that was going from D to E is redirected to go to F. Klem fra Nils Grimsmo 15:18, 20 November 2006 (UTC)

There is a small mistake in the pseudocode for the EdisonKarp algorithm. The flow returning is not computed correctly. It must be

...
while v ≠ s
u := P[v]
F[u,v] := F[u,v] + m
F[v,u] := F[v,u] - m
v := u
...

The net flow must be zero. --85.176.154.47 00:00, 24 January 2007 (UTC)

Oops. Thank you for notifying! Klem fra Nils Grimsmo 06:56, 24 January 2007 (UTC)

I believe there is another error in the pseudo code.

In the Breadthfirstsearch you do:

if (C[U,v] - F[u,v] > 0 and...)

But that is not a correct computation of the residual capacity. I believe it must be

if (C[U,v] - F[u,v] + F[v,u] > 0 and...)

Because a flow in one direction will increase the capacity in the other.

Note how values are updated when backtracking the path. The net flow is maintained. Skew symmetry is upheld. Klem fra Nils Grimsmo 20:29, 25 March 2007 (UTC)

At the end of the example it says that the minimal cut partitions the nodes into "sets {let A =6,B,C,E} and {D,F,G}, with the capacity c(A,D) + c(C,D) + c(E,G) = 3 + 1 + 1 = 5." But isn't the capacity here missing edge (D,E) with c(D,E) = 2 ? The capacity of the cut would then be 7 instead of 5. —Preceding unsigned comment added by 134.60.236.119 (talk) 15:15, 23 October 2007 (UTC)

No, the capacity is five. You should only count edges from the source set S to the sink set T. edge D,E is from T to S, and therefore does not increase the capacity. ArrowmanCoder (talk) 01:40, 20 February 2009 (UTC)

You state that "...and independently by Jack Edmonds and Richard Karp in 1972 (discovered earlier).". Well, that is usual in any science. Did anybody ask Dinic at what point in time he discovered the algorithm that is attributed to Edmonds and Karp? If not, then the remark "(discovered earlier)" should be removed. —Preceding unsigned comment added by 130.237.222.140 (talk) 14:52, 1 October 2008 (UTC)