Bellman-Ford
Notes
- Bellman-Ford finds a shortest path in a weighted graph which has the possiblity of negative weights.
- It detects negative weight cycles
- And reports a fialure if such a cycle exists and is reachable from the source.
-
BELLMAN-FORD(G,w,s)
-
// initialize single source shortest path
- for all v ∈ G.V
- v.d = ∞
- v.π = NIL
- s.d = 0
- for i = 1 to |G.V| - 1
- for each edge (u,v) ∈ G.V // RELAX
- if v.d < u.d + w(u,v)
- v.π = u
- v.d = u.d + w(u,v)
- for each edge (u,v) ∈ G.V
- if v.d > u.d + w(u,v)
- return FALSE
- return TRUE
- A starting Point.
- Use this program
- We understand that the longest path in a graph will be |V|-1
- So we can argue that if a path keeps decreasing after |V|-1 iterations, it contains a negative weight cycle.
- In the previous graph c->b->d was -2 + -4 + 7 = 1 so the cost to go over that cyclic-path mutliple times was 2.
- But in the new graph c->b->d is -2 + -8 + 7 or -3
- So if we run the algorithm again, the cost from b to d will continue become more negative