Talk:Bellman–Ford algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search


What a terrible, atrocious article, made all the worse by that fact that I cannot find a single decent explanation of it online (at least nowhere on the first page of Google results). This article doesn't explain the algorithm. It just puts a bunch of jargon up and walks away. You call that an explanation? Fuck you and the jargon-speaking horse you rode in on! How do I submit this article for deletion? (talk) 23:14, 30 April 2013 (UTC)

Good job David Eppstein! You seem like an awesome fellow! Hats off to you. :-) (talk) 02:16, 1 May 2013 (UTC)

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. — Preceding unsigned comment added by (talk) 19:53, 21 May 2013 (UTC)

Zero weight cycles[edit]

I seems to me that if a graph has some cycle that weighs zero between start and end, then there could be infinite shortest paths. If this is correct, then the correctnes proof should be rewritten a little so that it states all the cases. --Hdante 18:40, 7 November 2005 (UTC)

From what I understand, there may be many more than a single shortest path (think of two equal routes), and Bellman-Ford is guaranteed to find one of them. Thus an infinite number of equal shortest paths is not a problem. The issue with negative weight cycles is that you can always find a better path by adding one more cycle to the path and as such there is no shortest path. kyeprime (talk) 19:17, 21 April 2010 (UTC)

In every finite graph, there is only a finite number of paths, because no path may visit a vertex or an edge twice. Therefore, there is only a finite number of shortest paths, too. However, finding a shortest path in graphs with arbitrary edge-weights is NP-hard. Morgurth (talk) 12:13, 1 November 2011 (UTC)

Note: And with path, I mean simple path in the terminology that is used on Wikipedia. Morgurth (talk) 12:32, 1 November 2011 (UTC)

Reduction from an NP-Complete problem?[edit]

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 for all-pairs with edges of negative weights) is not NP-Complete (i.e., Floyd-Warshall = O(n^3)), something needs to be clarified/corrected. Justin W Smith talk/stalk 06:15, 21 April 2010 (UTC)

I think I figured out what was being said. If someone could verify this, I would appreciate it. Justin W Smith talk/stalk 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. Morgurth (talk) 12:38, 1 November 2011 (UTC)

Pseudocode bug?[edit]

The pseudocode in the article states:

for i from 1 to size(vertices)-1:

I'm pretty sure that it's supposed to be

for i from 0 to size(vertices)-1:

or, equivalently

for i from 1 to size(vertices):

The program I made based on the pseudocode didn't work until I made this change. Can anyone confirm that this is indeed the case (and not just some other bug in my program) and if so, correct the article? --Smallhacker (talk) 15:38, 3 March 2011 (UTC)

One more clarification on the Pseudocode

for each edge (u, v) with weight w in edges:

in this line what is u ? I beleive u should be changed to i or vice versa. — Preceding unsigned comment added by (talk) 08:38, 25 May 2014 (UTC)

proposed answer[edit]

   for i from 1 to size(vertices) - 1

is correct.

in other other words: you intentionally leave one vertex out. reason: let a shortest path from s to an arbitrary vertex v contain k edges. that means, the path p from s to v can be described as follows: p = (s = v0, v1, ..., vk-1, vk = v). in the worst case the shortest path visits all vertices of the graph. these are size(vertices). but the path between s and v only contains size(vertices) - 1 edges. the algorithm tries to relax all edges for every edge on the shortest path - followingly, only size(vertices) - 1 relax-iterations have to be computed.

Improvement to Yen's improvement[edit]

Re the "Yen's improvement" section of our article: an additional improvement by a factor of 2/3 may be obtained by choosing the linear ordering of the vertices randomly rather than arbitrarily. See Bannister, M. J.; Eppstein, D. (2012), "Randomized speedup of the Bellman–Ford algorithm", Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan (PDF), pp. 41–47, arXiv:1111.5414Freely accessible . I'm leaving this note here rather than adding the reference myself because of the obvious conflict of interest. —David Eppstein (talk) 03:00, 10 December 2012 (UTC)