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)