Talk:Bellman–Ford algorithm
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)
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)
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)
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)