Bellman-Ford algorithm - Why can edges be updated out of order?

The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $\infty$. Then the shortest path from $s$ to each vertex is computed; this goes on for $|V|-1$ iterations. My questions are:

• Why does there need to be $|V|-1$ iterations?
• Would it matter if I checked the edges in a different order?
Say, if I first check edges 1,2,3, but then on the second iteration I check 2,3,1.

MIT Prof. Eric said the order didn't matter, but this confuses me: wouldn't the algorithm incorrectly update a node based on edge $x_2$ if its value was dependent on the edge $x_1$ but $x_1$ is updated after $x_2$?

• Which implementation do you consider? The dynamic programming one does not have a problem with order, obviously; for others it may be non-trivial. – Raphael Nov 26 '12 at 11:52

Consider the shortest path from $s$ to $t$, $s, v_1, v_2, \dots, v_k, t$. This path consists of at most $|V|-1$ edges, because repeating a vertex in a shortest path is always a bad idea (or at least there is a shortest path which does not repeat vertices), if we do not have negative weight cycles.

In round one, we know that the edge $(s, v_1)$ will be relaxed, so the distance estimate for $v_1$ will be correct after this round. Note that we have no idea what $v_1$ is at this point, but as we've relaxed all edges, we must have relaxed this one as well. In round two, we relax $(v_1, v_2)$ at some point. We still have no idea what $v_1$ or $v_2$ are, but we know their distance estimates are correct.

Repeating this, after some round $k+1$, we have relaxed $(v_k, t)$, after which the distance estimate for $t$ is correct. We have no idea what $k$ is until the entire algorithm is over, but we know that it will happen at some point (assuming no negative weight cycles).

So, the crucial observation is that after round $i$, the $i$-th node of the shortest path must have its distance estimate set to the correct value. As the path is at most $|V|-1$ edges long, $|V|-1$ rounds suffices to find this shortest path. If a $|V|$th round still changes something, then something weird is going on: all paths should already be 'settled' to their final values, so we must have the situation that some negative weight cycle exists.

• I have a small doubt here.I believe |v|-1 is the worst case number of rounds after which the shortest path is calculated from s to t.Assume we have vertices s,v1,v2..vn,t.If the edges are chosen in this order say (s,v1),(v1,v2) .. (vn,t),then in a single iteration itself we will have the shortest path from s to t.This is just for understanding and in practical terms we don't know the order of edges being picked and hence |v|-1 rounds.Am I right ? – whokares Dec 11 '12 at 18:43
• @whokares: yes, you might get lucky and find the shortest path on the first round. You don't know for sure until the last round that the value you find really is the shortest path, but it might be. Dijkstra's algorithm essentially 'causes' this to happen: if all edges have nonnegative weights, then the priority queue used in Dijkstra's algorithm 'predicts' the order in which you should relax edges so you find all shortest paths in your first round of relaxations. – Alex ten Brink Dec 11 '12 at 19:28
• Thanks for the update.I got it.In one of the material ,its mentioned as <br>Slide 6 : A poor choice of relaxation order can lead to exponentially many relaxations:<br>Slide 8 : “Smart” order of edge relaxations <br> – whokares Dec 12 '12 at 8:22
• Irrespective of the order of edges in each iteration,the Shortest paths will be calculated in |v|-1 iterations right ? Why does he say exponential.Does he mean if we chose the same order for all iterations which we normally do ,the relaxation code will be called but updating the label for a vertex might happen only fewer number of times because of the order thereby saving processor time ? – whokares Dec 12 '12 at 8:23
• @whokares: the first algorithm they present (that can have exponential running time) does not relax all edges in a round, but instead finds some edge for which a relaxation operation would change something, and relaxes this edge. If you keep doing this and there is no negative weight cycle, then eventually no edges would help you any more and you stop. However, because you have no rounds and no set ordering on which edge to relax next, you might end up doing an exponential number of relaxations. The improved algorithm they present is Bellman-Ford, which does have rounds. – Alex ten Brink Dec 12 '12 at 22:45

The longest a path can be without any cycles is |V|. We start with a source, so we already have a path of length 1, so we need |V| - 1 more nodes to get the longest path.

The order doesn't matter because every order will maintain the invariant: after n iterations, the value for each node is less than or equal to the cost of the minimum cost path from s to the node containing at most n edges.

If, at the beginning of an iteration, the cost is correct up to n nodes, then at the end of the iteration it is correct up to n+1 nodes. A reordering can cause some nodes to have a lower cost before they would normally be updated, but they would eventually be updated anyway.

• I don't know if it just me, or I can't really visualise these facts easily. To me, I still think there might be some nodes that have not update within the V-1 iterations. – user1675999 Nov 26 '12 at 3:38
• No, you have |E|=|V|-1 edges when you have |V| nodes connected by a simple path without cycles. And you have |V|-1 iterations, delete your response because it's wrong. – Sam Aug 16 '18 at 8:33
• @sam Who are you and what does anything you say have to do with the answer? – fgb Aug 16 '18 at 11:49