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

Problem Detail: 

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$?

Asked By : user1675999

Answered By : Alex ten Brink

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6894