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

Solution:

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

V	1	2	3	4	5
d[v]	∞	∞	∞	∞	0
p[v]	/	/	/	/	–

Iteration 1:

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

V	1	2	3	4	5
d[v]	∞	4	∞	2	0
p[v]	/	5	/	5	–

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.

V	1	2	3	4	5
d[v]	7	3	3	2	0
p[v]	2	4	4	5	–

Iteration 3:

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

V	1	2	3	4	5
d[v]	6	3	3	2	0
p[v]	2	4	4	5	–

Iteration 4:

No edge relaxed

So the final shortest path from source vertex 5 is:

V	1	2	3	4	5
d[v]	6	3	3	2	0
p[v]	2	4	4	5	–

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, u₁.π = 2, u₂.π = 4, u₄.π = 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

u₁.d + w(1,3) < v₃.d ⇒  6 + 6 ≥ 4

u₁.d + w(1,4) < v₄.d ⇒  6 + 3 ≥ 2

u₂.d + w(2,1) < v₁.d ⇒  3 + 3 ≥ 6

u₃.d + w(3,4) < v₄.d ⇒ 3 + 2 ≥ 2

u₄.d + w(4,2) < v₂.d ⇒ 2 + 1 ≥ 3

u₄.d + w(4,3) < v₃.d ⇒ 2 + 1 ≥ 3

u₅.d + w(5,2) < v₂.d ⇒ 0 + 4 ≥ 3

u₅.d + w(5,4) < v₄.d ⇒ 0 + 2 ≥ 2

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

Some Popular Problems Solved using Dynamic Programming

• Binomial Coefficient
• Making a Change
• Knapsack Problem
• Multistate Graph Problem
• Optimal Binary Search Tree
• Matrix Chain Multiplication
• Longest Common Subsequence
• Bellman-Ford (Single Source Shortest Path) Algorithm
• Floyd-Warshall (All Pair Shortest Path) Problem
• Assembly Line Scheduling
• Travelling Salseman Problem
• Flow Shop Scheduling

---

Additional Reading: [Wiki]