Let V be the set of vertices in a graph. I understand that given a graph of |V| vertices with no negative cycles, a shortest path will always have |V|-1 edges. I still don't quite understand why checking every edge |V|-1 times guarantees that Bellman Ford's algorithm will produce the shortest path. Can someone help me understand this better?
4 Answers
In the first phase (checking every edge once), you consider all potential shortest paths with only one edge. So if the shortest path has only one edge, you will have found it after the first phase. (But you don't yet know that you've found the shortest path.)
After the second phase of checking all edges, you will have considered all potential paths of two edges, since you consider all possible extensions by one edge of the paths you already considered. So if the shortest path has at most two edges, you will have found it after the second phase.
And so on… If the shortest path has at most |V|−1 edges (which it does), you will have found it after |V|−1 phases.
This is done in the relaxation step. In this step, vertice distances are updated incrementally. Intuitively, these updates are propagated throughout the graph: When you find a shorter path to one node, then its neighbours might also benefit from this shortcut. In the next iteration, they get updated too, and so on.
But this updating cannot continue indefinitely. The maximum number of times it can occur is precisely |V| - 1. You can visualise it as a path of updates propagating from one vertex, throughout all other vertices, back to the source. The source itself of course does not find a shortcut to itself.
In my opinion, it's necessary to do some math to understand it fully (although the other answers already give some intuition). Let's prove the following statement by induction:
Let s be the source vertex and u be any other vertex in the directed graph. After i iterations of Bellman-ford algorithm:
- if d[u] is not infinity, it is equal to the length of some path from s to u.
- if there is a path from s to u with at most i edges, then d[u] is at most the length of the shortest path from s to u with at most i edges.
Proof
The base case is i=0 (before any iteration). At this moment, d[s] = 0 and d[u] = ∞ for all u. It's obvious that (1) and (2) are valid for this case.
Let's consider that it's valid for i (inductive hypothesis).
At the i+1 iteration, consider a moment when a vertex v distance is updated by d[v] := d[u] + w[u][v]. By the inductive hypothesis, d[u] is the length of some path from s to u. Then d[u] + w[u][v] is the length of the path from source to v that follows the path from source to u and then goes to v. So, (1) is valid for the (i+1)-th iteration and by induction is valid for all natural i.
Now, consider a shortest path P (there may be more than one) from s to v with at most i+1 edges. Let u be the last vertex before v on this path. Then, the part of the path from s to u is a shortest path from s to u with at most i edges. Indeed, suppose that it's not. Then there would exist some strictly shorter path from s to u with at most i edges, which could be appended to the edge uv to obtain a path with at most i edges that is strictly shorter than P, which is contradiction. By inductive hypothesis, d[u] after i iterations is at most the length of the shortest path from s to u. Therefore, d[u] + w[u][v] is at most the length of P. In the (i+1)-th iteration, d[v] gets compared with d[u] + w[u][v], and is set equal to it if d[u] + w[u][v] is smaller. Therefore, after i+1 iterations, d[v] is at most the length of P, which is a shortest path from s to v that uses at most i+1 edges. So, (2) is valid for the (i+1)-th iteration and by induction is valid for all natural i.
To finish, notice that if the directed graph has |V| vertices and no negative cycles, a shortest path from a source s to a vertex u has at most |V| - 1 edges. So, by the previous result, Bellman-Ford indeed find all shortest paths from s.
Notice that The Bellman-Ford Algorithm is based on a recursive relationship, which states that:
d(i,v) is the shortest distance from the source to each node v with at most i edges between them.
As i grows to i+1, you allow one more edge, and you update the path length only if it improves.
Since we know that the shortest path can have at most n-1 edges, there is no point to grow i further, i.e, the shortest path has to be:
d(n-1,v).
Related