[go: up one dir, main page]
Scribd
Upload
24 views23 pages

Bellman-Ford Algorithm-Single Source Shortest Path

The Bellman-Ford algorithm computes the shortest paths from a single source vertex to all other vertices in a directed graph, even in the presence of negative-weight edges. It can also detect negative-weight cycles, indicating that some shortest paths may not exist. The algorithm guarantees that if there are no negative cycles, the shortest path between any two vertices will have at most n - 1 edges.

Uploaded by

yashaswimannem
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
24 views23 pages

Bellman-Ford Algorithm-Single Source Shortest Path

The Bellman-Ford algorithm computes the shortest paths from a single source vertex to all other vertices in a directed graph, even in the presence of negative-weight edges. It can also detect negative-weight cycles, indicating that some shortest paths may not exist. The algorithm guarantees that if there are no negative cycles, the shortest path between any two vertices will have at most n - 1 edges.

Uploaded by

yashaswimannem
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/ 23

Bellman‐Ford algorithm -

Single‐source shortest paths


Bellman‐Ford algorithm
• Single‐source shortest paths
• Handling negative‐weight cycles and negative
edges
Negative-weight cycles
Recall: If a graph G = (V, E) contains a negative-
weight cycle, then some shortest paths may not exist.

Bellman-Ford algorithm: Finds all shortest-path


lengths from a source s  V to all v  V or
determines that a negative-weight cycle exists.
Recall: Single‐
Source Shortest
• Paths
Problem: Given a directed
graph with edge‐weight , and
functionvertex , compute
source a
for all
– Also want shortest‐path tree represented
by
Example: 0 1
1
5 A B 3
2 7
0 s 2 t 4

−2 C D 10
3
−2 8
• When there are no cycles of negative length, there is a shortest path between any
two vertices of an n-vertex graph that has at most n -1 edges on it

• a path that has more than n – 1 edges must repeat at least one vertex and hence
must contain a cycle.
Example of Bellman-Ford

t 5 x
-2
6 ¥ ¥
-3
s 8
0 -4 7
2
7
¥ 9 ¥
y z
Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31


L18.
Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31


L18.
Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31


L18.
Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31


L18.
Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31


L18.
Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.


Example of Bellman-Ford

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.


Example of Bellman-Ford

Note: Values decrease


monotonically.
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.
Bellman-Ford Algorithm
Example
t 5 x
-2
6 ¥ ¥
-3
s 8
0 -4 7
2
7
¥ 9 ¥
y z
Bellman-Ford Algorithm
Example
t 5 x
-2
6 6 ¥
-3
s 8
0 -4 7
2
7
7 9 ¥
y z
Bellman-Ford Algorithm
Example
t 5 x
-2
6 6 4
-3
s 8
0 -4 7
2
7
7 9 2
y z
Bellman-Ford Algorithm
Example
t 5 x
-2
6 2 4
-3
s 8
0 -4 7
2
7
7 9 2
y z
Bellman-Ford Algorithm
Example
t 5 x
-2
6 2 4
-3
s 8
0 -4 7
2
7
7 9 -2
y z

You might also like