Content deleted Content added
No edit summary |
No edit summary |
||
Line 5:
::According to Cormen et al's ''Introduction to Algorithms, 2nd edition'', the breadth-first search is done to reduce the search time from <math>O(E|f^*|)</math> to <math>O(VE^2)</math> (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.--[[User:Kristjan Wager|Kristjan Wager]] 14:09, 31 May 2005 (UTC)
::No, the <math>O(E|f^*|)</math> 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]]. --[[User:Zero0000|Zero]] 20:08, 31 May 2005 (UTC)
| |||