Scribd
Upload
187 views27 pages

BellMAN Ford Algorithm

The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It works by iteratively relaxing edges to update the distance labels, taking negative edge weights into account to detect negative cycles. The algorithm initializes all distances as infinity, then iterates through the edges to relax and update distances until it has iterated V-1 times where V is the number of vertices, or detects a negative cycle.

Uploaded by

Vinila Jinny S
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
187 views27 pages

BellMAN Ford Algorithm

The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It works by iteratively relaxing edges to update the distance labels, taking negative edge weights into account to detect negative cycles. The algorithm initializes all distances as infinity, then iterates through the edges to relax and update distances until it has iterated V-1 times where V is the number of vertices, or detects a negative cycle.

Uploaded by

Vinila Jinny S
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 27

BELLMAN FORD

ALGORITHM
Module-4
Dr. S. Vinila Jinny
ASP/SCOPE
Bellman-Ford algorithm
Bellman-Ford algorithm

Initialize all the


distances
Bellman-Ford algorithm

iterate over all


edges/vertices
and apply update
rule
Bellman-Ford algorithm
Bellman-Ford algorithm

check for negative


cycles
Negative cycles

What is the shortest path


from a to e?

1
1 B D

5
A
10 -10

C E
3
Bellman-Ford algorithm
Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A:
2
1 1

-2
F C

-1 3
E D
-1
Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
F C

-1 3
E D
-1
Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B:
F
-1 3
E D
-1
Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B: 5
F
-1 3
E D
-1
Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B: 5
F
-1 3
E D D:
-1
Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B: 5
F
-1 3
E D D: 7
-1
Bellman-Ford algorithm
0 
10
S A Iteration: 0
8 1

 G -4 B
2
1 1

-2 
F C

-1 3
E D
-1
 
Bellman-Ford algorithm
0 10
10
S A Iteration: 1
8 1

8 -4 B
G
2
1 1

-2 
F C

-1 3
E D
-1
 
Bellman-Ford algorithm
0 10
10
S A Iteration: 2
8 1

8 -4 B
G
2
1 1

-2 
F C
9

-1 3
E D
-1
12 
Bellman-Ford algorithm
0 5
10
S A Iteration: 3
8 1
10

8 G -4 B A has the correct


2 distance and path
1 1

-2 
F C
9

-1 3
E D
-1
8 
Bellman-Ford algorithm
0 5
10
S A Iteration: 4
8 1
6

8 -4 B
G
2
1 1

-2 11
F C
9

-1 3
E D
-1
7 
Bellman-Ford algorithm
0 5
10
S A Iteration: 5
8 1
5

8 G -4 B B has the correct


2 distance and path
1 1

-2 7
F C
9

-1 3
E D
-1
7 14
Bellman-Ford algorithm
0 5
10
S A Iteration: 6
8 1
5

8 -4 B
G
2
1 1

-2 6
F C
9

-1 3
E D
-1
7 10
Bellman-Ford algorithm
0 5
10
S A Iteration: 7
8 1
5

8 G -4 B D (and all other


2 nodes) have the
1 1 correct distance
and path
-2 6
F C
9

-1 3
E D
-1
7 9
Correctness of Bellman-Ford
• Loop invariant:
Correctness of Bellman-Ford
• Loop invariant: After iteration i, all vertices with
shortest paths from s of length i edges or less have
correct distances
Runtime of Bellman-Ford

O(|V| |E|)
Runtime of Bellman-Ford

Can you modify the algorithm to run


faster (in some circumstances)?
All pairs shortest paths
• Simple approach
• Call Bellman-Ford |V| times
• O(|V|2 |E|)
• Floyd-Warshall – Θ(|V|3)
• Johnson’s algorithm – O(|V|2 log |V| + |V| |E|)

You might also like