Bellman-Ford Algorithm: Difference between revisions
No edit summary |
|||
| Line 6: | Line 6: | ||
= 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 16: | Line 20: | ||
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 = | ||
Revision as of 05:53, 9 March 2024
Approach: dynamic programming
All shortest path must have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq |V| - 1 } 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} to node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} with at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n - 1} edges.
The main loop iterates Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n - 1} 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)
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(n-1, a) = min(w(b,a) + OPT(n-2, b) \forall (b, a) \in E)}
Implementation
Time complexity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^2 + VE) }
- Sparse: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^2) }
- Dense: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^3) }
// 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.
