Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 17:03, 23 March 2010

Revision as of 03:56, 24 March 2010

Line 10:

{{WikiProject Computing|class=|importance=}}

{{archives}}

== More Explanation on Negative Cycles Needed ==

I think the "Behaviour with negative cycles" is not clear enough.

When there is a negative cycle in the graph,does the output has any meaning?

Can anyone explain it?[[User:Visame|Visame]] ([[User talk:Visame|talk]]) 17:28, 7 March 2008 (UTC)

:Basically, there is no solution to the shortest-path problem in a graph with negative cycles any machine can represent. You can think of it as the following: Assume you have a cycle C in a graph, and the overall sum of edge weights of this cycle is W. Furthermore, assume that this cycle contains a vertex V. If you now consider a path which goes like v_1, v_2, ..., V, ..., v_n, with an overall path weight P, then you can extend this path as follows: v_1, v_2, ..., V, C, V, ..., v_n. This works, since V is contained in the circle C, and thus, you can walk through the circle and end up at V again. Clearly, we can repeat this as much as we want, so v_1, ..., V, C, ..., C, V, ..., v_n, with as many C's as one likes all are still good paths through the graph. Now, consider the overall weight of these expanded paths. Without the circles, the overall weight of the path was P, but now, with one circle added to expand the graph, the new weight will be P + W, or, with K cycles added into the path, the new weight will be P + K*W. Now there are two cases: If W is positive (W > 0), then it clearly holds that P < P + W < P + 2*W < ..., thus, a correct shortest path algorithm will ignore them. However, if W is negative (W < 0), then it clearly holds that P > P + W > P + 2*W, ..., as you subtract more, and more and more from the path length. Thus, there exists no shortest path in this graph, as for whatever path you declare the shortest one, I can construct a shorter path by using P and adding enough repetitions of the circle into P. Now, Floyd-Warshall is one of the nicer algorithms to handle this, as Floyd-Warshall just stops after a certain number of iterations and outputting paths with a certain negative weight, because the number of edges on a path considered by the Floyd-Warshall-algorithm is bounded, thus, the output is wrong (even though, as the article states, negative cycles can be detected by checking the diagonal elements: dist[v][v] describes the weight of circles containing V, which is exactly what I described earlier). I hope this helps, and if it does, it can be added to the article (Probably with a nice image to make it really clear) --[[User:Tetha|Tetha]] ([[User talk:Tetha|talk]]) 14:02, 3 September 2009 (UTC)

== FW no longer in the c++ boost library ==

They currently only list the Johnson algorithm, no FW (presumably because it's slower). I think if I blindly removed the link from the page it would get rv'd quickly. [[Special:Contributions/134.173.201.55|134.173.201.55]] ([[User talk:134.173.201.55|talk]]) 09:08, 13 April 2009 (UTC)

== Notation style ==