# Talk:Bellman–Ford algorithm

## 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)

## 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)

## 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)

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 49.203.64.216 (talk) 08:38, 25 May 2014 (UTC)

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