Talk:Floyd–Warshall algorithm

Mathematics B‑class Mid‑priority

This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. B This article has been rated as B-class on Wikipedia's content assessment scale. Mid This article has been rated as Mid-priority on the project's priority scale.

Computer science B‑class High‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. B This article has been rated as B-class on Wikipedia's content assessment scale. High This article has been rated as High-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Archives

Archive 1

This page has archives. Sections older than 95 days may be auto-archived by Lowercase sigmabot III if there are more than 4.

Applications and generalizations

Latest comment: 15 years ago2 comments2 people in discussion

• 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 —Preceding unsigned comment added by 209.94.128.120 (talk) 04:56, 1 December 2009 (UTC)Reply

${\displaystyle 1}$  in position ${\displaystyle (i,j)}$  in this variant of the algorithm means that we already know that there is a path between vertices ${\displaystyle i}$  and ${\displaystyle j}$ . If you want to combine paths ${\displaystyle i\rightarrow k}$  and ${\displaystyle k\rightarrow j}$  (where you would use addition of their lengths in the usual variant), you have to use AND (you can go from ${\displaystyle i}$  to ${\displaystyle j}$  through ${\displaystyle k}$  if there is a path between ${\displaystyle i}$  and ${\displaystyle k}$  AND there is a path between ${\displaystyle k}$  and ${\displaystyle j}$ ). When you try to decide whether there is path through ${\displaystyle k}$  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 ${\displaystyle 0}$  in this variant. Svick (talk) 11:31, 1 December 2009 (UTC)Reply

Undirected Graphs

Latest comment: 12 years ago3 comments3 people in discussion

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. AlexandreZ (talk) 16:13, 23 March 2010 (UTC)Reply

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. Jwesley₇₈ 17:03, 23 March 2010 (UTC)Reply

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. Dcoetzee 21:02, 19 December 2012 (UTC)Reply

Java examples

Latest comment: 15 years ago2 comments2 people in discussion

I explored both examples of the FW algorithm implemented in Java. The one in commons.apache.org is a link into the source tree of a long-dormant project that never achieved release status, is very poorly documented, and is nearly impenetrable without a long exploration of the source tree. (In fairness, it is architected as an element of a library.) The one on AlgoWiki is straightforward and simple, with the supporting code readily available.

I propose that we remove the reference to the commons example from the article body. If you don't want to lose the reference, put it in the exterior links section, or as a ref. Dmforcier (talk) 18:36, 8 August 2010 (UTC)Reply

I don't think those links should be in the article body at all. Few of them should be moved to External links, and the rest deleted. Svick (talk) 20:21, 8 August 2010 (UTC)Reply

First sentence

Latest comment: 13 years ago2 comments2 people in discussion

The article begins, "In Computer Science...". Doesn't this seem a bit pretentious and misleading? Floyd-Warshall's Algorithm has many different and unique applications, and it is certainly neither confined to the field of computer science nor dependent on computer science. If such a presumptive lead-in is to be used--I don't see a need for such a one, in my opinion it's unnecessary--then the most generalized, pure categorization should be used, e.g. "In Graph Theory..." or, "In Mathematics...". Cheers. — Preceding unsigned comment added by 71.12.211.253 (talk) 21:45, 12 June 2012 (UTC)Reply

It's standard for Mathematics and Computer Science articles to begin with "In <field of study>...". And this article is about an algorithm! The algorithm computes the length of the shortest path between any two vertices, but I don't think that beginning the article with "in graph theory" would be more accurate. Justin W Smith ^talk/_stalk 03:05, 13 June 2012 (UTC)Reply

Optimization in Pseudocode

Latest comment: 12 years ago1 comment1 person in discussion

I've removed the optimization from the pseudocode. The point of pseudocode is not to show the most efficient method possible, but rather to illustrate how the algorithm works. It is implicitly expected that programmers should take simple optimizations into account. Stargazer7121 (talk) 21:39, 8 February 2013 (UTC)Reply