Dr.

Mohammed Hussein
Analysis of Algorithms

The Bellman-Ford algorithm

DR. MOHAMMED AL-HUBAISHI

1
 2
Introduction to the Bellman-
Ford Algorithm

► The Bellman-Ford algorithm is a shortest path

algorithm that is used to find the shortest path
between two nodes in a weighted graph. It
was invented by Richard Bellman and Lester
Ford Jr. in 1958.
► The algorithm works by iterating through all
the edges of the graph multiple times,
relaxing each edge on every iteration. The
relaxation process involves updating the
distance and predecessor of each vertex if a
shorter path is found.

Dr. Mohammed Hussein

 3
Single-Source Shortest Path Problem

Single-Source Shortest Path Problem - The problem of

finding shortest paths from a source vertex v to all other
vertices in the graph.

Bellman-Ford algorithm is a single-source

shortest path algorithm that is used to find
the shortest path between a source node
and all other nodes in a weighted graph. It
can handle negative weight edges and
cycles in the graph.

Dr. Mohammed Hussein

 4
Understanding the Bellman-
Ford Algorithm

► The Bellman-Ford algorithm can handle graphs with negative

weight edges, which sets it apart from other shortest path
algorithms like Dijkstra's algorithm.
► However, the algorithm has a higher time complexity compared to
Dijkstra's algorithm. This is because it iterates through all the edges
of the graph multiple times, making it slower for larger graphs.

Dr. Mohammed Hussein

 5
Implementing the Bellman-
Ford Algorithm

► To implement the Bellman-Ford algorithm, we start by initializing

the distance to the source node as 0 and the distance to all
other nodes as infinity. We also set the predecessor of all nodes to
null.
► We then iterate through all the edges of the graph V-1 times,
relaxing each edge on every iteration. After the final iteration, we
check for negative weight cycles. If there are any negative
weight cycles, the algorithm returns an error since there is no
shortest path.

The time complexity of Bellman-Ford algorithm is O(VE) where V is the

number of vertices and E is the number of edges in the graph.

Dr. Mohammed Hussein

 6
Bellman-Ford algorithm example
on an undirected graph

The algorithm initializes the distance to the source

node as zero and all other distances to infinity. Then, it
relaxes each edge in the graph for V-1 times where V
is the number of vertices in the graph. During every
relaxation, the algorithm updates the distance from
the source to the destination vertex if there exists a
shorter path from the source to the destination
through an intermediate vertex.

If the graph contains a negative weight cycle, then

the shortest path distance may not exist and the
algorithm will detect this cycle during the V-1
iterations. At this point, the algorithm returns an error
message indicating the presence of a negative
weight cycle.
Dr. Mohammed Hussein Shortest path: 0 3 4 2
 7
ex1

6
7
4 8
7 3

5
9 4

8
2
6

Shortest path: 0 1 4 5
Dr. Mohammed Hussein
17
 8
ex2

6
7
4 18
7 3

5
9 4

8
2
6

Shortest path: 0 1 2 3 4 5

Dr. Mohammed Hussein 26

 9
ex3

6
7
4 -18
7 3

5
9 4

8
2
6

Shortest path: 0 1 4 5

Dr. Mohammed Hussein

-9
 10
example on a directed graph

7
4 Update
2
1 If (d[u]+c(u,v)<d[v])
2 d[v]= d[u]+c(u,v)
1 2 6
0 1

4 5

3 5
3

Dr. Mohammed Hussein

 11

Shortest Path Problem

⮚ Weighted path length (cost): The sum of the weights of all links on the
path.

⮚ The single-source shortest path problem: Given a weighted graph G and

a source vertex s, find the shortest (minimum cost) path from s to every
other vertex in G.

Dr. Mohammed Hussein

 12
Differences

⮚ Negative link weight: The Bellman-Ford algorithm works; Dijkstra’s

algorithm doesn’t.

⮚ Distributed implementation: The Bellman-Ford algorithm can be easily

implemented in a distributed way. Dijkstra’s algorithm cannot.

⮚ Time complexity: The Bellman-Ford algorithm is higher than Dijkstra’s

algorithm.

Dr. Mohammed Hussein

 13
example

https://onlinegdb.com/8fUjfHcFH

Dr. Mohammed Hussein

 14
C++ code

Dr. Mohammed Hussein

 15
pseudocode for Bellman-Ford
Algorithm

Dr. Mohammed Hussein

16
 The Bellman-Ford Algorithm 17

pseudocode

Bellman-Ford(G, w, s)
1. Initialize-Single-Source(G, s)
2. for i := 1 to |V| - 1 do
3. for each edge (u, v) ∈ E do
4. Update (u, v, w)
5. for each vertex v ∈ u.adj do
6. if d[v] > d[u] + w(u, v)
7. then return False // there is a negative
cycle
8. return True Update (u, v, w)
if d[v] > d[u] + w(u, v)
then d[v] := d[u] + w(u, v)
Dr. Mohammed Hussein
parent[v] := u
 18
Time Complexity

Bellman-Ford(G, w, s)
1. Initialize-Single-Source(G, s) O(|V|)
2. for i := 1 to |V| - 1 do
3. for each edge (u, v) ∈ E do
4. Relax(u, v, w) O(|V||E|)
5. for each vertex v ∈ u.adj do O(|E|)
6. if d[v] > d[u] + w(u, v)
7. then return False // there is a
negative cycle
8. return True
Dr. Mohammed Hussein

Time complexity: O(|V||E|)

 19
Bellman-Ford example

-2
0 4
4 -nf
1 2
5 -10
4 3
5 3 8 V d[v]
-nf -nf 1 0

Edge= (1,4),(1,2),(4,3),(3,2) 2 -2
3 8
4 5
Dr. Mohammed Hussein
 Example directed weighted graph
0
1
2
3
5
6
-1 -nf
-nf 5
2
3
6 -2 3
1 7 5
5 3 3
0 1 7
5 3 8
5 -2
-nf -nf
6
4 -1 4
5
-nf -nf

Edge= (1,2),(1,3), (1,4),(2,5), (3,2),(3,5), (4,3),(4,6) , (5,7),(6,7)

Dr. Mohammed Hussein
 21

results

Relaxation -1
5
If (d[u]+c(u,v)<d[v]) 2 O(E*(V-1))
d[v]= d[u]+c(u,v) 3
-2 O(E*V)
6
V d[v 1 O(n^2)
7
] 5 3
0 1
1 0 3
2 1 5 -2
3 3
6
4 5 4 -1
5 0
6 4 Edge= (1,2),(1,3), (1,4),(2,5), (3,2),(3,5), (4,3),(4,6) , (5,7),(6,7)
7 3
Dr. Mohammed Hussein
 22
homework

4
1 2
5 5 -10
4 3
3

Edge= (3,2),(4,3), (1,4),(1,2) ,(2,4)

Dr. Mohammed Hussein

 23
Homework:

Dr. Mohammed Hussein

 24
Homework:

Dr. Mohammed Hussein

 25
Homework:

Dr. Mohammed Hussein

Shortest path: 0 7 6 5 4
 26

Dr. Mohammed Hussein

 27

Dr. Mohammed Hussein

 28

Dr. Mohammed Hussein

 29

Dr. Mohammed Hussein

 30

Dr. Mohammed Hussein

 Real-World Applications of the 31
Bellman-Ford Algorithm

► The Bellman-Ford algorithm is used in various real-world

applications such as network routing protocols, traffic flow
analysis, and airline scheduling.
► In network routing protocols, the algorithm is used to find
the shortest path between two nodes in a network. In
traffic flow analysis, it is used to optimize traffic flow by
finding the shortest path between intersections. In airline
scheduling, it is used to determine the most efficient routes
for flights.

Dr. Mohammed Hussein

 32
Advancements in the Bellman-
Ford Algorithm

► Over the years, various advancements have been made to

the Bellman-Ford algorithm to improve its efficiency. One such
advancement is the use of heuristics to reduce the number of
iterations needed to find the shortest path.
► Another advancement is the use of parallel computing to
speed up the algorithm for larger graphs. These advancements
have made the algorithm more practical for real-world
applications.

Dr. Mohammed Hussein

 33
Q1

► What is the time complexity of Bellman-Ford

algorithm?
(A) O(V^2)
(B) O(VE)
(C) O(V^3)
(D) O(E^2)
The answer is (B). Bellman-Ford algorithm is an iterative
algorithm that takes O(VE) time.

Dr. Mohammed Hussein

 34
Q2

► What is the space complexity of Bellman-Ford

algorithm?
(A) O(V)
(B) O(E)
(C) O(V^2)
(D) O(E^2)
► The answer is (A). Bellman-Ford algorithm only needs
to store the distances to each vertex, which takes
O(V) space.

Dr. Mohammed Hussein

 35
Q3

► What is the difference between Bellman-Ford algorithm and Dijkstra's algorithm?

(A) Bellman-Ford algorithm can handle negative edge weights, while Dijkstra's algorithm
cannot.
(B) Bellman-Ford algorithm is an iterative algorithm, while Dijkstra's algorithm is a recursive
algorithm.
(C) Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other
vertices, while Dijkstra's algorithm finds the shortest paths from a single source vertex to a
single destination vertex.
(D) All of the above.
► The answer is (D). Bellman-Ford algorithm can handle negative edge weights, while
Dijkstra's algorithm cannot. Bellman-Ford algorithm is an iterative algorithm, while
Dijkstra's algorithm is a recursive algorithm. Bellman-Ford algorithm finds the shortest
paths from a single source vertex to all other vertices, while Dijkstra's algorithm finds
the shortest paths from a single source vertex to a single destination vertex.
Dr. Mohammed Hussein
 36
Q4

► What is the worst case running time of Bellman-Ford

algorithm?
(A) O(V^2)
(B) O(VE)
(C) O(V^3)
(D) O(E^2)
► The answer is (C). The worst case running time of
Bellman-Ford algorithm is O(V^3). This is because the
algorithm has to iterate over all edges V times, and
each iteration could potentially update all vertices V
times.

Dr. Mohammed Hussein

 37
Q5

► What is the best case running time of Bellman-Ford

algorithm?
(A) O(V)
(B) O(E)
(C) O(V^2)
(D) O(E^2)
► The answer is (A). The best case running time of Bellman-
Ford algorithm is O(V). This is because if there are no
negative edge weights, then the algorithm can find the
shortest paths from a single source vertex to all other
vertices in a single iteration.

Dr. Mohammed Hussein

 38
Conclusion

► The Bellman-Ford algorithm is a powerful tool for finding the

shortest path between two nodes in a weighted graph. Its
ability to handle negative weight edges makes it a valuable
asset in various real-world applications.
► While the algorithm may have a higher time complexity
compared to other shortest path algorithms, advancements
in technology have made it more efficient and practical for
larger graphs.

Dr. Mohammed Hussein