Content deleted Content added
m something more reasonable |
AlexandreZ (talk | contribs) →Undirected Graphs: new section |
||
Line 120:
:<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)
| |||