Bellman Ford Algorithm: Single Source Shortest Path Algorithm

Bellman Ford algorithm is used to find the shortest path from the source vertex to remaining all other vertices in the weighted graph. We can find an optimal solution to this problem using dynamic programming.

  • It is slower compared to Dijkstra’s algorithm but it can handle negative weights also.
  • If the graph contains negative –weight cycle (edge sum of the cycle is negative), it is not possible to find the minimum path, because on every iteration of cycle gives a better result.
  • Bellman Ford algorithm can detect a negative cycle in the graph but it cannot find the solution for such graphs.
  • Like Dijkstra, this algorithm is also based on the principle of relaxation. The pathis updated with better values until it reaches the optimal value.
  • Dijkstra uses apriority queue to greedily select the closest vertex and perform relaxation on all its adjacent outgoing edges. By contrast, Bellman Ford relaxes all the edges |V|- 1 time. Bellman Ford runs in O(|V|.|E|) time.

Algorithm

Algorithm BELLMAN-FORD (G)

// Description : Find the shortest path from source vertex to all other vertices using Bellman-Ford algorithm

// Inputs : 
Weighted graph G = (V, E, W) 
w(u, v): Weight of edge (u, v)
d[u] : distance of vertex u from source
π[u]: Successor of vertex u

// Output: Shortest distance of each vertex from given source vertex.

// Initialization
for v ∈ V do
    d[v] ← ∞
    π[v] ← NULL
end

d[s] ← 0

// Relaxation
for i ← 1 to |V| - 1 do
    for each edge (u, v) ∈ E do
        if d[u] + w (u, v) < d[v] then
            d[v] ← d[u] + w(u, v)
            π[v] ← u
        end
    end
end

// Check for negative cycle
for each edge (u, v) ∈ E do
    if d[u] + w(u, v) < d[v] then
        error “Graph contains negative cycle”
    end
end
return d, π

Examples of Bellman Ford Algorithm

Example: Find the shortest path from source vertex 5 for a given graph

Bellman Ford Algorithm

Solution:

Initialize the distance: Set distance of source vertex to 0 and every other vertex to ∞.

V12345
d[v]0
p[v]////
Bellman Ford Algorithm example

Iteration 1:

Edges <5, 2> and <5, 4> will be relaxed as their distance will be updated to 4 and 2 respectively.

V12345
d[v]420
p[v]/5/5
Bellman Ford Algorithm solution

Iteration 2:

Edges <2, 1>, <4, 3> and <2, 4> will be relaxed as their distance will be updated to 7, 3 and 3 respectively.

V12345
d[v]73320
p[v]2445
Example of Bellman Ford Algorithm

Iteration 3:

Edge <2, 1>will be relaxed as its distance will be updated to 6.

V12345
d[v]63320
p[v]2445

Iteration 4:

No edge relaxed

So the final shortest path from source vertex 5 is:

V12345
d[v]63320
p[v]2445

The shortest path from any vertex can be found by starting at the vertex and following its predecessor π’s back to the source. For example, starting at vertex 1, u1.π = 2, u2.π = 4, u4.π = 5 ⇒ the shortest path to vertex 1 is {5, 4, 2, 1}.

Negative cycle check:

We have to test following condition for each edge.

if

d[u] + w(u, v) < d[v] 

then


    error “Graph contains negative cycle”

end

u1.d + w(1,3) < v3.d ⇒  6 + 6 ≥ 4

u1.d + w(1,4) < v4.d ⇒  6 + 3 ≥ 2

u2.d + w(2,1) < v1.d ⇒  3 + 3 ≥ 6

u3.d + w(3,4) < v4.d ⇒ 3 + 2 ≥ 2

u4.d + w(4,2) < v2.d ⇒ 2 + 1 ≥ 3

u4.d + w(4,3) < v3.d ⇒ 2 + 1 ≥ 3

u5.d + w(5,2) < v2.d ⇒ 0 + 4 ≥ 3

u5.d + w(5,4) < v4.d ⇒ 0 + 2 ≥ 2

None of the above conditions are satisfied, so the graph does not contain any negative cycle.


Additional Reading: [Wiki]

You may also like...

Leave a Reply

Your email address will not be published.