Content deleted Content added
Line 115:
The lead cites a reduction by Sedgewick from the [[NP-Complete]] [[Hamiltonian path problem]] to the [[shortest path problem]]. Since the shortest path problem (even <ins>for all-pairs</ins> with <ins>edges of</ins> negative weight<del>s</del>) is not NP-Complete (i.e., Floyd-Warshall = O(n^3)), something needs to be clarified/corrected. <b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i> 06:15, 21 April 2010 (UTC)
: I think I figured out what was being said. If someone could verify this, I would appreciate it. <b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i> 14:08, 21 April 2010 (UTC)
The shortest path problem with arbitrary edge-weights is NP-hard. Moore-Bellman-Ford and Floyd-Warshall work only on graphs with conservative edge weights, i.e., there may be no cycles of negative total weight. [[User:Morgurth|Morgurth]] ([[User talk:Morgurth|talk]]) 12:19, 1 November 2011 (UTC)
== Pseudocode bug? ==
| |||