Bellman-Ford Algorithm
Approach: dynamic programming
All shortest path must have edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.
The idea is to add one edge at a time, seeing if the edge should be included in the shortest path.
Recurrence
Let OPT(n-1, a) be the length of the shortest path from source node to node with at most edges.
The main loop iterates times. Inside each iteration, each edge is relaxed once.
By relaxing every edge, we add a possible edge to the shortest path. Since there is at most n - 1 edges in the shortest path, we iterate n - 1 times.
If we don't add the edge, the length is OPT(n - 2, a)
If we add the edge, the length would be OPT(n - 2, b) + w(b, a)
Implementation
Time complexity:
- Sparse:
- Dense:
// G: Graph with vertices (V) and edges (E) // w[e]: weight of edge e // S: starting node Bellman-Ford(G, w, S) V, E = G pi[v] = null for all v // traceback // initialize all shortest path algo d[v] = infty for all v d[s] = 0 for i from 1 to |V| - 1: for all (u,v) in E if d[v] > d[u] + w(u, v): d[v] = d[u] + w(u,v) pi[v] = u; for all (u, v) in E: if d[v] > d[u] + w(u, v): // has negative cycle return false
This accounts for negative edges but not negative cycles. Bellman Ford can detect it by running an extra time, since if there is a negative cycle, the run time will improve.