Talk:Floyd–Warshall algorithm

Mathematics B‑class Mid‑priority

	Mathematics portal 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

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 automatically archived by when more than 4 sections are present.

Java examples

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

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

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 expected that programmers will take simple optimizations into account. Stargazer7121 (talk) 21:39, 8 February 2013 (UTC)[reply]

Path reconstruction Incorrect

The Path reconstruction pseudocode never populates the 'next' variable with anything but null and so it cannot find any paths. 67.172.248.52 (talk) 16:19, 14 October 2013 (UTC)[reply]

Negative Cycles

In my opinion the section about negative cycles is wrong in the sense that it is stated that there is no shortest path, because traversing the cycles multiple times makes the length arbitrarily small. But in the context of shortest paths one usually talks about (simple) paths and not walks, i.e., multiple traversal is not allowed. And then of course (since there are only finitely many simple paths), a shortest path is well-defined. In this case, the algorithm just fails since the concatenation of the shortest i-(k+1)-path and the shortest (k+1)-j-path (both using only vertices 1 up to k as inner vertices) does not necessarily result in a simple path since it may contain a cycle.

MatthiasWalter (talk) 08:51, 10 December 2013 (UTC)[reply]