Revision as of 05:41, 21 April 2010 edit SineBot (talk \| contribs) Bots 2,564,861 edits m Signing comment by 78.157.76.143 - "" ← Previous edit		Revision as of 06:15, 21 April 2010 edit undo Justin W Smith (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 5,998 edits Reduction from an NP-Complete problem? Next edit →
Line 86: Introduction says: "Bellman-Ford cannot find the shortest path that does not repeat any vertex in such a graph". I can't understand this sentence at all. Did someone want to say that B-F cannot find the negative cycle, it is only able to detect it? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/78.157.76.143\|78.157.76.143]] ([[User talk:78.157.76.143\|talk]]) 05:41, 21 April 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--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 with negative weights) is not NP-Complete, 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)

Talk:Bellman–Ford algorithm: Difference between revisions