Bellman-Ford Algorithm: Difference between revisions
No edit summary |
No edit summary |
||
(5 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
{{Infobox Algorithm|runtime=O(V^2 | {{Infobox Algorithm | ||
|runtime=<math>O(V^2 E)</math> | |||
|class=[[Dynamic Programming]] <br> [[Graph Algorithms]] <br> [[Shortest Path Problem]] | |||
}} | |||
== Bellman-Ford Algorithm == | |||
The Bellman-Ford algorithm is a solution to the [[Shortest Path Problem|shortest path problem]]. It works for graphs with real-number weights, and is capable of detecting negative edge loops. | |||
= 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. | ||
The idea is to add one edge at a time, seeing if the edge should be included in the shortest path. | |||
==== Recurrence ==== | ==== Recurrence ==== | ||
Let OPT(n-1, a) be the length of the shortest path from source node <math>s</math> to node <math>a</math> with at most <math>n - 1</math> edges. | Let OPT(n-1, a) be the length of the shortest path from source node <math>s</math> to node <math>a</math> with at most <math>n - 1</math> edges. | ||
The | The main loop iterates <math> n - 1</math> 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 don't add the edge, the length is OPT(n - 2, a) | ||
Line 14: | Line 24: | ||
If we add the edge, the length would be OPT(n - 2, b) + w(b, a) | If we add the edge, the length would be OPT(n - 2, b) + w(b, a) | ||
OPT( | <math> OPT(n-1, a) = min(w(b,a) + OPT(n-2, b) \forall (b, a) \in E)</math> | ||
= Implementation = | = Implementation = |
Latest revision as of 00:30, 13 March 2024
Bellman-Ford Algorithm
The Bellman-Ford algorithm is a solution to the shortest path problem. It works for graphs with real-number weights, and is capable of detecting negative edge loops.
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.