Shortest Path Problem: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 26: | Line 26: | ||
Time complexity: <math> O(V^2) </math> | Time complexity: <math> O(V^2) </math> | ||
<pre> | <pre> | ||
for | // 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 | |||
</pre> | </pre> | ||
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. |
Revision as of 02:00, 28 February 2024
Definitions
A path is a sequence of nodes such that for all consecutive nodes, there exist an edge
Let there be a weight assigned to each edge.
Single Source Shortest Path (SSSP)
Given a graph , source node , outupt the shortest path from the source
Variants
- Single destination problem: shortest path from all nodes to a single destination
- Single pair problem: Shortest path between input pair
Implementation: Bellman Ford
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.
OPT(a, n-1) = min(w(u,a) + OPT(n-1, u) for all (u, a) in E)
Time complexity:
// 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.