Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 16:19, 14 October 2013

Revision as of 19:26, 21 October 2013

Line 10:

{{WikiProject Computer science|class=B|importance=high}}

{{archives}}

== Applications and generalizations ==

* Transitive closure of directed graphs (Warshall's algorithm). In Warshall's original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).

I think the AND and OR operations are mixed up here. AND would result in 0 for all pairs except 1,1 which is the only pair with a minimum of 1, and OR is the logical operator for addition. Didn't want to change the main page b/c I don't actually know for sure if this is correct but it struck me as wrong when I saw it. -rockychat3 <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/209.94.128.120|209.94.128.120]] ([[User talk:209.94.128.120|talk]]) 04:56, 1 December 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:<math>1</math> in position <math>(i, j)</math> in this variant of the algorithm means that we already know that there is a path between vertices <math>i</math> and <math>j</math>. If you want to combine paths <math>i \rightarrow k</math> and <math>k \rightarrow j</math> (where you would use addition of their lengths in the usual variant), you have to use AND (you can go from <math>i</math> to <math>j</math> through <math>k</math> if there is a path between <math>i</math> and <math>k</math> AND there is a path between <math>k</math> and <math>j</math>). When you try to decide whether there is path through <math>k</math> OR “direct” (i.e. one we already know) path, you use OR. The difference stems from the fact that “no path” is represented as infinity in the usual algorithm, but as <math>0</math> in this variant. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 11:31, 1 December 2009 (UTC)

== Undirected Graphs ==

Weighted undirected graphs are equally capable of being solved by the Floyd-Warshall algorithm though some small changes are needed to gain further optimization. I've made the changes to have the article reflect that fact. [[User:AlexandreZ|AlexandreZ]] ([[User talk:AlexandreZ|talk]]) 16:13, 23 March 2010 (UTC)

: ''Undirected'' graphs are essentially a special case for ''directed'' graphs, especially sine F-W works only with the incidence matrix. You're right that one can optimize away half of the comparisons if you know beforehand that the graph is undirected. However, I think that this detail is not needed, nor is that optimization commonly used. <b><font color="green">Jwesley</font>[[User_talk:Jwesley78|₇₈]]</b> 17:03, 23 March 2010 (UTC)

: An undirected graph must have no negative cycles to have well-defined shortest paths. It would be exceedingly strange to use Floyd-Warshall instead of running Dijkstra from all vertices on a graph with non-negative weights. [[User:Dcoetzee|Dcoetzee]] 21:02, 19 December 2012 (UTC)

== Java examples ==