CSE 2202: Algorithm Analysis and Design Laboratory

Bellman-Ford Algorithm
Most. Kaniz Fatema Isha
Md Mehrab Hossain Opi
 Problem with Dijkstra 2
• Previously we learned Dijkstra’s Algorithm.
• Do you know what is the problem with this algorithm.
• Consider the following graph.

2
2 -2
1 2 3
-5
4

• What is the cost of the shortest path from node 1 to node 3?

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Negative Weight 3
•

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Problem with Dijkstra’s Algorithm 4
• Negative weight edges can create negative weight cycles.
• a cycle that will reduce the total path distance by coming back to the same point.

• Dijkstra’s algorithm does not work if the graph contains a negative cycle.
• Going through a cycle reduces path length and produces wrong result.

• Today we will learn a new algorithm that works on graph with negative cycles.
• The algorithm is called Bellman-Ford Algorithm.

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 5
• Like Dijkstra’s Algorithm, Bellman-Ford algorithm also uses relaxation.
• Do you remember what relaxation is?

The process of relaxing an edge (u,v) consists of testing whether going through vertex u
improves the shortest path to vertex v found so far and, if so, updating distance[v]

• In Dijkstra’s Algorithm, we only used the outgoing edges of a selected node in each
iteration.
• Hope you can remember it.

• But in Bellman-Ford algorithm, we will use all the edges in each iteration.

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 6
• Let’s see how Bellman-Ford Algorithm works now.
• We will consider the following graph

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 7
•

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 8
• Let node number 0 be the source node.
• We will set the distance of node 0 to 0.

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 9
• Now we will start our iteration of relaxation.
• In each iteration we will try to relax all the edge.

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 10
•

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 11
•

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 12
•

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Bellman-Ford Algorithm 13
Edge Weigh Edge Relaxation
t
(0,1) 2
(4,6) 2
(3,4) 10
(0,2) 6
(5,6) 6 4
1
(2,3) 1
2 6 10 2
(1,3) 6
0 3 6
(5,3) 15
6 1 6
15

2 5

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 The Algorithm 14
• After iterating through all the edges one time we get the following distances.

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

• Have we got the shortest distance for all the nodes?

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 The Algorithm 15
• We need to iterate through all the edges again.
• After second iteration we get the following distances.

1 4

2 6 10 2

0 3 6

6 1 6
15

2 5

• We still don’t have the shortest distance of node 6.

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 The Algorithm 16
•

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Reasoning 17
• What happens when we iterate through all edges for the first time?
• After the first iteration, we guarantee that the shortest paths using at most one edge are
found.
• After the second iteration, the shortest paths using at most two edges are found, and so
on.

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Reasoning 18

can have at most 𝑉−1 edges.

• The shortest path between any two vertices in a graph with no negative weight cycles

• A path with more than 𝑉−1 edges would necessarily involve revisiting some vertices,
implying a cycle.

𝑉−1) would be the shortest, 𝑉−1 iterations are sufficient.

• Since cycles can only increase the number of edges and the path with fewer edges (up to

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Time Complexity 19
•

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Negative Cycle Detection 20
• To detect if the graph contains any negative cycle reachable from source, we relax all the
edges 1 more times.
• If the distance of any node is updated, we can say a negative cycle exist.

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 Pseudocode 21
•
0 G is a weighted directed graph.
1 V is the set of vertices.
E is the set of edges.
-2 G = (V,E)
1 2 s is the source node.
1 -5
3

1
The function returns True
4 if no negative cycle exists.

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024

 References 22
• Introduction to Algorithm, 4th ed, Leiserson, Charles Eric, Ronald L. Rivest, Thomas H.
Cormen, and Clifford Stein.
• Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 – GeeksforGeeks
• Dijkstra's Shortest Path Algorithm using priority_queue of STL - GeeksforGeeks
• Dijkstra on sparse graphs - Algorithms for Competitive Programming (cp-algorithms.com)

CSE 2202: Algorithm Analysis and Design Laboratory September 5, 2024