Talk:Bellman–Ford algorithm/Archive 1

Archive 1

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(V³) 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:

http://xkcd.com/69/

--Jake 01:04, 11 September 2007 (UTC)

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)

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)

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)

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)

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.

~ Booya ^Bazooka 20:50, 5 October 2009 (UTC)

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)

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)

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) 

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)

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)

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)

RELAX?!?!? DON'T TELL ME TO RELAX WITHOUT DEFINING IT!!!

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? 98.180.51.94 (talk) 23:14, 30 April 2013 (UTC)

Good job David Eppstein! You seem like an awesome fellow! Hats off to you. :-) 98.180.51.94 (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 84.203.48.54 (talk) 19:53, 21 May 2013 (UTC)

Pop up shortest-path figure

The "shortest path" link in the first sentence pops up a figure whose caption refers to edge weights, yet the figure doesn't show any. Mdmi (talk) 21:25, 2 April 2019 (UTC)

That is an issue with the shortest path problem article, not with this article. The pop-up always picks the first image in the article, and the first image of that article was not a particularly useful one. —David Eppstein (talk) 00:05, 3 April 2019 (UTC)