yeah can find a decent step by step guide to this on line. one that describes each detail of each step otherwise im not going to get it. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84.203.48.54|84.203.48.54]] ([[User talk:84.203.48.54|talk]]) 19:53, 21 May 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
==Reduction from an NP-Complete problem?==
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 (simple) 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. In fact, MBF and FW compute a shortest walk with at most |V|-1 edges. In the case of conservative edge weights, these happen to be shortest (simple) paths. If there are negative cycles, this is not true. [[User:Morgurth|Morgurth]] ([[User talk:Morgurth|talk]]) 12:38, 1 November 2011 (UTC)
