Talk:Bellman–Ford algorithm
 | Mathematics B‑class Low‑priority | |||||||||
| ||||||||||
 | Computer science Unassessed Mid‑importance | ||||||||||||||||
| |||||||||||||||||
Assembly code
Assembly code has no place in algorithm articles; it doesn't help explain the algorithm at all.
I removed the license notice and the attribution to "JellyWorld" from the C code. Fortunately, the license was GFDL-compatible, and it permitted the attribution to be removed.
RSpeer 17:46, Apr 21, 2005 (UTC)
I changed the problem from weighted graph to weighted *digraph* because Bellman Ford fails spectacularly on undirected graphs: If there is a negative weight edge, say {u, v}, then Bellman-Ford will get stuck updating u and v foreover, even if there is no negative weight cycle. This subtlety may be worth mentioning in the main article. To find shortest paths in undirected graphs with negative edge weights, you can reduce the problem to weighted nonbipartite matching.
If both loops cycle directly through the number of vertexes (on the top loop) and on the edges (the second one), how come it would be "forever"? In such a loop there's no way it will be infinit. Or am I picturing the whole thing wrong? —Preceding unsigned comment added by 87.196.85.225 (talk) 02:02, 19 February 2009 (UTC)
Negative weight cycles
Please cite a source saying that Bellman-Ford can be used to find simple paths on networks with negative cycles, or else correct this section. All sources I can find say that simple paths cannot be found on a network with negative cycles. This includes Wolfram's implementation of Bellman-Ford, as well as Yen's 1971 paper "Finding the k shortest loopless paths in a network" published in Management Science (vol 17, no 11). Corman's book cited in the article also states that Bellman-Ford can't find paths in networks with negative cycles. —Preceding unsigned comment added by ToneDaBass (talk • contribs) 02:15, 3 August 2010 (UTC)
Zero weight cycles
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)
Counting to infinity
I didn't know what "counting to infinity" meant in the list of limitations of the distributed algorithm, so I searched around a bit and added a few words expressing what I found. But if anyone has a better explanation, please do add. -- Orbst 15:29, 17 April 2006 (UTC)
How do you compile the C code?
That would be nice if you can modify the C source code so that it compiles with gcc. When I copy/paste the code and compiles it with gcc, it gives me:
/usr/lib/gcc/powerpc-linux-gnu/3.4.5/../../../../lib/crt1.o:(.rodata+0x4): undefined reference to `main' collect2: ld returned 1 exit status
- Defining main() would probably be a good start. :P Compiling to object code works just fine; you've forgotten the "-o" flag to gcc. 164.55.254.106 18:51, 31 May 2006 (UTC)
Computational complexity
Could you add info about computational complexity of the algorithm? ~~helix84 22:37, 4 October 2006 (UTC)
In the worst case this algorithm uses O(V3) time in order to find single-source shortest paths. This is not very efficient. By a slight modification it can find all-pairs shortest paths in the same time. Tomo 08:13, 16 December 2006 (UTC)
sizeof
Comparing sizeof(int) and sizeof *distance form which both acomplish the same thing. The former form is much more idiom and recognisable to most programmers, the second is a less common form. Indeed the The C Book says the form without brackets is rarely used. This particular instance is confusing for two reasons a) the * could be mistaken for multiplication b) as distance is declared on the same line it provokes the question as to whether the compiler knows about the size of *distance yet. If we are aiming more maximum comprehensability the former seems perferable. --Salix alba (talk) 00:55, 19 May 2007 (UTC)
In popular culture
I don't know that this is encyclopedia worthy, but for folks working on this page, this might be an amusing reference:
A doubt
Are we sure this is the Bellman-Ford algorithm and not the generic labeling method? There's a source in which Bellman-Ford is described as an optimization of the labeling algorithm using a FIFO queue. (http://avglab.com/andrew/pub/neci-tr-96-029.ps). This is just a question, I am right now confused because of different sources describing a very different algorithm. Vexorian (talk) 13:01, 17 January 2009 (UTC)
FIFO Bellman-Ford is an optimization for the Bellman-Ford algorithm. The generic relabel-relax method is defined differently, informal description follows:
generic relabel-relax:
// I Initialize
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null
// II Loop
while (edge uv that can be relaxed) exists:
relax (u, v, λ) — Preceding unsigned comment added by 188.192.84.92 (talk) 11:54, 3 September 2011 (UTC)
Undefined Terms
This article uses the terms "relax" and "relaxation" in a specific technical sense, but gives no definition. The use of undefined terms in mathematical writing is considered poor form. -- 172.191.112.126 (talk) 23:08, 25 February 2009 (UTC)
Very much agreed, I have found many definitions of this and many other algorithms all with lack of definition of specific terms. —Preceding unsigned comment added by 66.119.173.210 (talk) 17:11, 15 May 2009 (UTC)
Dijkstra is not greedy
The Shortest-Path-Problem for graphs with non-negative-weights doesn't have a matroid or greedoid structure. Therefore this problem cannot be solved by an greedy-algorithm. Therefore Dijkstra is not greedy. —Preceding unsigned comment added by 131.220.109.37 (talk) 09:29, 23 March 2009 (UTC)
- Have you read the Wikipedia article on Dijkstra's algorithm? Both that article and this one make a pretty good case for calling Dijkstra's algorithm "greedy" (in comparison to algorithms like this one that are more "open-minded" and can't be "tricked" by promising paths that turn out to be dead ends). See also Google. I don't know what "matroid or greedoid structure" has to do with this article; I guess you're talking about a very highly specialized use of the word "greedy" that this article isn't using. Anyway, it would make sense to take this up at Talk:Dijkstra's algorithm, at least until that article stops referring to Dijkstra's algorithm as "greedy". :) --Quuxplusone (talk) 06:45, 24 March 2009 (UTC)
Bellmam ford algorithm can be used in the network having negative terms in the nodes.I —Preceding unsigned comment added by 59.98.124.227 (talk) 06:38, 24 March 2009 (UTC)
The greedoid page that you linked to explicitly lists Dijkstra's algorithm as an example. So, uh, yeah. —Preceding unsigned comment added by 68.43.177.99 (talk) 16:31, 7 May 2009 (UTC)
Implementation removed
I removed the "C implementation" section. This seems to be out of place in a wikipedia article. There is already the pseudocode, which conveys how that algorithm works. The C code is quite long, difficult to verify, and redundant. And a GFDL license is not really useful for sharing code. There is also a discussion at [1] that led me here. — Carl (CBM · talk) 00:24, 8 April 2009 (UTC)
As hard as an NP-complete problem
The last paragraph in the summary, regarding "the shortest path that does not repeat any vertex in such a graph", states:
- "This problem is at least as hard as the NP-complete longest path problem."
This seems like a very silly expression. Doesn't it just mean that the problem at least as hard as any NP-complete problem - which can be best stated by just calling it NP-hard? ~ Booya Bazooka 23:02, 4 October 2009 (UTC)
Perhaps what we should say is more along the lines of
- This problem is NP-hard, which can be shown via a reduction to the longest path problem.
Path vs. Walk
The article consistently mentions path (which, by definition, is required to not duplicate any vertex) when it means walk (any sequence of adjacent edges, repeating vertices are possible). This should be imho fixed... In fact, Bellman-Ford algorithm finds shortest walks of length at most n. Requiring shortest paths is what makes the problem hard. —Preceding unsigned comment added by 129.132.153.228 (talk) 12:44, 4 February 2010 (UTC)
Unclarity
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? —Preceding unsigned comment added by 78.157.76.143 (talk) 05:41, 21 April 2010 (UTC)
- I made several changes. Hopefully, it's a little clearer. Justin W Smith talk/stalk 06:16, 21 April 2010 (UTC)
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 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?
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)
proposed answer
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
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.5414. 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)