Talk:Ford-Fulkerson algorithm

From Wikipedia, the free encyclopedia

Algorithms by nature terminate. this article is full of references to "whether the algorithm terminates" and "a variation which is guaranteed to terminate". these phrases are problematic! is F-F not an algorithm at all, but an approach/procedure? Aaronbrick 04:34, 12 May 2006 (UTC)

This is a valid point. This entry should actually be called the Ford-Fulkerson Method. It's not called an algorithm, because there is some part in the procedure which is left unspecified. The Ford-Fulkerson Method says that you need to keep finding augmenting paths in the residual graph, but does not limit you to any specific way of finding those augmenting paths. That is exactly why the procedure may never terminate, as described in the body of the article. On the other hand, an algorithm should always terminate with an answer, or with announcing that no answer can be found. That is the basic criteria for decidability, and an algorithm is formally defined to be a procedure for testing membership for decidable languages. —Preceding unsigned comment added by 128.227.179.104 (talk) 02:58, 11 October 2007 (UTC)

[edit] Error in example_2.svg

The middle arrow from should point from C to B, not from B to C.

[edit] Errors in the Algorithm Section

There seems to be a slight error in the "Algorithm" section. There are three formulas with three informal descriptions next to them. The informal descriptions for the second and third seem to have been interchanged. In short, it is:

2. f(u,v)=-f(v,u) - We maintain the net flow.
3. sum(f(u,v))=0 for all nodes except s and t - The amount of flow into a node equals the flow out of the node.

whereas it should be:

2. f(u,v)=-f(v,u) - The amount of flow into a node equals the flow out of the node.
3. sum(f(u,v))=0 for all nodes except s and t - We maintain the net flow.

I would also suggest replacing "for all nodes" with "for all nodes u" for clarity.

Viridium 03:27, 10 April 2007 (UTC)

The wording is perhaps a bit unclear. By "maintaining the net flow", it is meant that if there are in reality going for example 5 trucks from u to v, and 3 trucks from v to u, then we maintain f(u,v) = 2 and f(v,u) = − 2, such that f(u,v) = − f(v,u). For the third invariant, it might get clearer if written
\sum_v f(u,v) = 0 \Longleftrightarrow \sum_v f_-(u,v) + \sum_v f_+(u,v) = 0 \Longleftrightarrow \sum_v f_-(u,v) = \sum_v f_+(u,v) \Longleftrightarrow f_{in}(u) = f_{out}(u)
where f − is only the negative values, and f + only the positive. Klem fra Nils Grimsmo 05:39, 11 April 2007 (UTC

Nice clarification but some detail is wrong there (in equation above). There is a minus sign missing. Where this minus sign should go depends on which convention you use for the defintion of f − (u,v) : Is it the absolute value of the negative flow, or is it the actual negative flow complete with its numerical negativity?

In the example, I don't see how the possibility of flow directly along ABD is skipped at the second step, given that this example of bad behaviour is claiming to result from depth first search. Surely, in an alphabetic "depth first search", path ABD should be tried next -- before ACBD is tried! --Preceding unsigned comment left by 128.227.179.104 02:58, 11 October 2007 (UTC)

The depth-first search must not be alphabetic - it seems to be actively worst-case. That sort of thing can happen if the edges are stored in a nondeterministic, unordered set instead of a matrix. It's pretty unlikely, but that's what worst-case means. --Brilliand 22:58, 26 October 2007 (UTC)