Bellman-Ford Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
{{Infobox Algorithm|runtime=O(V^2 + E)}} | {{Infobox Algorithm|runtime=O(V^2 + E)}} | ||
= Approach: dynamic programming = | = Approach: dynamic programming = | ||
All shortest path must have <math> \leq |V| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest. | All shortest path must have <math> \leq |V| - 1 </math> edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest. |
Revision as of 00:02, 6 March 2024
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.
Recurrence
Let OPT(n-1, a) be the length of the shortest path from source node to node with at most edges.
The idea is to add one edge at a time, seeing if the edge should be included in the shortest path.
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)
OPT(a, n-1) = min(w(b,a) + OPT(n-1, b) for all (b, a) in E)
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.