PowerPoint Presentation
Faculty of Information Technology,
Monash University
FIT2004: Algorithms and Data Structures
Week 9: Bellman Ford and Floyd-Warshall Algorithms
These slides are prepared by M. A. Cheema and are based on the material developed by Arun Konagurthu and Lloyd Allison.
Recommended reading
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Unit notes: Chapter 13
Cormen et al. Introduction to Algorithms.
Section 24.1 Bellman-Ford Algorithm
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Directed/
Outline
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Shortest path in a graph with negative weights
All-pairs shortest paths
Transitive Closure
Shortest path (negative weights)
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
What is the shortest distance from s to x in this graph?
What will be the shortest distance from s to x if Dijkstra’s algorithm is used on this graph?
6
7
4
5
-3
9
– 4
7
– 2
Shortest path (negative weights)
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
What is the shortest distance from s to x in this graph?
What will be the shortest distance from s to x if Dijkstra’s algorithm is used on this graph?
6
7
4
5
-3
9
– 4
7
– 2
Shortest path (negative weights)
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
What is the shortest distance from s to x in this graph?
What will be the shortest distance from s to x if Dijkstra’s algorithm is used on this graph?
Dijkstra’s algorithm cannot handle graph with negative weights.
How to compute shortest paths on such graphs?
Bellman-Ford Algorithm
6
7
4
5
-3
9
– 4
7
– 2
Dijkstra’s
Graph with –ve weights
Shortest path (negative weights)
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
If there is a negative cycle in the graph, the notion of shortest path/distance does not make sense.
Note that Dijkstra can handle negative weights in some cases
Bellman-Ford algorithm returns
shortest distances from s to all vertices in the graph if there are no negative cycles
an error if there is a negative cycle reachable from s (i.e., can be used to detect negative cycles)
Can be modified to return all valid shortest distances, and minus ∞ for vertices which are affected by the negative cycle
Bellman-Ford Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
Initialize:
For each vertex a in the graph
dist(s,a) = ∞
dist(s,s) = 0
Consider the following operation (relaxation):
For each edge (a, b, w) in the graph // the order does not matter
dist(s, b) = min(dist(s,b) , dist(s,a) + w)
6
7
4
5
-3
9
– 4
7
– 2
0
∞
∞
∞
∞
Assume the following order:
(u,t), (u,v), (u,x), (t,u), (v,t), (v,x), (x,t), (s,u), (s,v)
Example done by hand in lecture
Bellman-Ford Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
6
7
8
5
-3
9
– 4
7
– 2
0
6
7
∞
∞
Assume the following order:
(u,t), (u,v), (u,x), (t,u), (v,t), (v,x), (x,t), (s,u), (s,v)
Initialize:
For each vertex a in the graph
dist(s,a) = ∞
dist(s,s) = 0
Consider the following operation (relaxation):
For each edge (a, b, w) in the graph // the order does not matter
dist(s, b) = min(dist(s,b) , dist(s,a) + w)
Bellman-Ford Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
6
7
8
5
-3
9
– 4
7
– 2
0
6
7
2
4
Assume the following order:
(u,t), (u,v), (u,x), (t,u), (v,t), (v,x), (x,t), (s,u), (s,v)
Initialize:
For each vertex a in the graph
dist(s,a) = ∞
dist(s,s) = 0
Consider the following operation (relaxation):
For each edge (a, b, w) in the graph // the order does not matter
dist(s, b) = min(dist(s,b) , dist(s,a) + w)
Bellman-Ford Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
6
7
8
5
-3
9
– 4
7
– 2
0
2
7
2
4
Assume the following order:
(u,t), (u,v), (u,x), (t,u), (v,t), (v,x), (x,t), (s,u), (s,v)
–
Initialize:
For each vertex a in the graph
dist(s,a) = ∞
dist(s,s) = 0
Consider the following operation (relaxation):
For each edge (a, b, w) in the graph // the order does not matter
dist(s, b) = min(dist(s,b) , dist(s,a) + w)
Bellman-Ford Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
# STEP 1: Initializations
dist[1…V] = infinity
pred[1…V] = Null
dist[s] = 0
# STEP 2: Iteratively estimate dist[v] (from source s)
for i = 1 to V-1:
for each edge
est = dist[u] + w
if est < dist[v]:
dist[v] = est
pred[v] = u
# STEP 3: Checks and returns false if a negative weight cycle
# is along the path from s to any other vertex
for each edge
if dist[u]+w < dist[v] :
return error; # negative edge cylce found in this graph
return dist[...], pred[...]
Time Complexity:
O(VE)
Bellman-Ford Algorithm: Correctness
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
We established that the negative cycles do not make sense
Can a shortest path from s to t have a positive cycle (i.e., with weight more than zero)?
No, because the path that avoids this cycle will have smaller distance
Also, if the path has a zero-weight cycle, it can be ignored
i.e., shortest distances can be computed by ignoring the non-negative cycles
What is the maximum number of edges in a shortest path between two vertices ignoring zero-weight cycles?
V - 1
Bellman-Ford Algorithm: Correctness
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
A fact from last week: If P is a shortest path from s to u, and v is the last vertex on P before u, then the part of P from s to v is also a shortest path
Suppose there was a shorter path from s to v, say Q
Weight(Q) + uv < weight(P)
But P is the shortest path from s to u
Contradiction
s
v
u
P
Q
Bellman-Ford Algorithm: Correctness
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
After i repetitions
Invariant1: If dist[u] is not inf, then it is the length of some path from s to u
Invariant2: If there is path from s to u with at most i edges, then dist[u] is at most the length of the shortest path from s to u with at most i edges
Base case, i=0:
All distances except s are inf
There are no paths with 0 edges from s to any non-s vertex
Inductive step for inv1:
Consider the moment when a distance of a vertex is updated by dist[u] = dist[v] + weight(vu).
By inductive assumption dist[v] is the length of some path from s to v, we have also found a path from s to u
Bellman-Ford Algorithm: Correctness
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
After i repetitions
Invariant1: If dist[u] is not inf, then it is the length of some path from s to u
Invariant2: If there is path from s to u with at most i edges, then dist[u] is at most the length of the shortest path from s to u with at most i edges
Inductive step (before iteration i):
Consider a shortest path P from s to u with at most i edges (we have not found this path yet, we are going to find it in iteration i)
Let v be the last vertex before u on P
So P without vu is a shortest path from s to u (of length i-1)
Bellman-Ford Algorithm: Correctness
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
After i repetitions
Invariant1: If dist[u] is not inf, then it is the length of some path from s to u
Invariant2: If there is path from s to u with at most i edges, then dist[u] is at most the length of the shortest path from s to u with at most i edges
Inductive step (before iteration i):
By assumption, dist[v] is at most the length of the shortest path from s to u with at most i-1 edges
So dist[v] + weight(vu) is at most the length of P
Since we compare dist[u] with dist[v] + weight(vu) in interation i, we will find P if it is better than dist[u]
So after i iterations, dist[u] is at most the length of the shortest path from s to u (since that is what we assumed P to be)
Bellman-Ford Algorithm: Negative Cycles
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
v
u
x
t
s
If V-th iteration reduces the distance of a vertex, this means that there is a shortest path with at least V edges which implies that there is a negative cycle.
Consider the graph with vertices s, u, v, and t and assume we have run (V-1 = 3) iterations.
In the 4th iteration, the weight of at least one vertex will be reduced (due to the presence of a negative cycle).
Important: Bellman-Ford Algorithm finds negative cycles only if such cycle is reachable from the source vertex
E.g., if x is the source vertex, the algorithm will not detect the negative cycle
7
4
-3
9
- 2
0
2
7
4
6
Bellman-Ford Algorithm: Negative Cycles
How could we modify Bellman-Ford to determine which vertices have valid distances, and which are affected by the negative cycle?
Hint:
The Vth iteration tells us that a negative cycle exists
Which vertices must reachable from the negative cycle after the Vth iteration?
Outline
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Shortest path in a graph with negative weights
All-pairs shortest paths
Transitive Closure
All-Pairs Shortest Paths
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Problem
Return shortest distances between all pairs of vertices in a connected graph.
For unweighted graphs:
For each vertex v in the graph
Call Breadth-First Search for v
Time complexity:
O(V(V+E)) = O(V2 + EV) O(EV) [for connected graphs O(V) ≤ O(E)]
For dense graphs: E is O(V2), therefore total cost is O(V3 ) for dense graphs
All-Pairs Shortest Paths
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
For weighted graphs (with non-negative weights):
For each vertex v in the graph
Call Dijkstra’s algorithm for v
Time complexity:
O(V(E log V)) = O(EV log V)
For dense graphs: O(V3 log V)
All-Pairs Shortest Paths
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
For weighted graphs (allowing negative weights):
For each vertex v in the graph
Call Bellman-Ford algorithm for v
Time complexity:
O(V(VE)) = O(V2 E)
For dense graphs: O(V4 )
Can we do better?
Yes, Floyd-Warshall Algorithm returns all-pairs shortest distances in O(V3 ) for graphs allowing negative weights.
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 3 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 3 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 2 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 2 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
2
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 2 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
2
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 2 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
2
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 2 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
BA exists, but AD is currently inf, so we cannot update BD
2
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
First iteration of outer loop (i.e., k is A):
Which shortcut(s) ij is/are updated/created after the execution of the inner for-loop?
A B C D
A 0 Inf -2 Inf
B 4 0 2 Inf
C Inf Inf 0 2
D Inf -1 Inf 0
2
Example done by hand in lecture
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Initialize adjacency matrix called dist[][] considering adjacent edges only
For each vertex k in the graph
For each pair of vertices i and j in the graph
If dist(i k j) is smaller than the current dist(ij)
Update/create shortcut i j with weight equal to dist(ikj)
i.e., update dist[i][j] = dist[i][k] + dist[k][j]
B
C
D
A
-2
4
3
2
-1
Assume that the outer for-loop will access vertices in the order A, B, C, D
A B C D
A 0 -1 -2 0
B 4 0 2 4
C 5 1 0 2
D 3 -1 1 0
Floyd-Warshall Algorithm
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
dist[][] = E # Initialize adjacency matrix using E
for vertex k in 1..V:
#Invariant: dist[i][j] corresponds to the shortest path from i to j considering the intermediate vertices 1 to k-1
for vertex i in 1..V:
for vertex j in 1..V:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Time Complexity:
O(V3)
Space Complexity:
O(V2)
Floyd-Warshall Algorithm: Correctness
Invariant: dist[i][j] corresponds to the shortest path from i to j considering only intermediate vertices 1 to k-1
Base Case k = 1 (i.e. there are no intermediate vertices yet):
It is true because dist[][] is initialized based only on the adjacent edges
Inductive Step:
Assume dist[i][j] is the shortest path from i to j detouring through only vertices 1 to k-1
Adding the k-th vertex to the “detour pool” can only help if the best path detours through k
Thus, minimum of dist(ikj) and dist(ij) gives the minimum distance from i to j considering the intermediate vertices 1 to k
Floyd-Warshall Algorithm: Correctness
Invariant: dist[i][j] corresponds to the shortest path from i to j considering only intermediate vertices 1 to k-1
Adding the k-th vertex to the “detour pool” can only help if the best path detours through k
We already know the best way to get from i to k (using only vertices in 1…k-1) and we know the best way to get from j to k (using only vertices in 1…k-1)
Thus, minimum of dist(ikj) and dist(ij) gives the minimum distance from i to j considering the intermediate vertices 1 to k
Floyd-Warshall Algorithm: Negative Cycles
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
If there is a negative cycle, there will be a vertex v such that dist[v][v] is negative.
Look at the diagonal of the adjacency matrix and return error if a negative value is found
How could you modify the algorithm to know which vertices have “real” distances, and which are affected by the negative cycle?
How could you modify the algorithm to return the paths?
A
B
C
D
A
0
-5
-3
B
5
-2
-1
C
0
D
-2
-1
-3
-1
B
C
D
A
-2
6
2
-2
-1
-5
1
3
4
-3
Floyd-Warshall Algorithm: Negative Cycles
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Bellman-Ford algorithm may not find a negative cycle if it is not reachable from the source vertex
Floyd-Warshall guarantees that it can find negative cycles
Outline
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Shortest path in a graph with negative weights
All-pairs shortest paths
Transitive Closure
Transitive Closure of a Graph
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Given a graph G = (V,E), its transitive closure is another graph (V,E’) that contains the same vertices V but contains an edge from every u to v if there is a path from u to v in the original graph.
Solution: Assign each edge a weight 1 and then apply Floyd-Warshall algorithm. If dist[i][j] is not infinity, this means there is a path from i to j in the original graph. (Or just maintain True and False as shown next)
u
t
s
v
x
u
t
s
v
x
Transitive Closure
Floyd-Warshall Algorithm for Transitive Closure
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
# Modify Floyd-Warshall Algorithm to compute Transitive Closure
# initialization
for vertex i in 1..V:
for vertex j in 1..V:
if there is an edge between i and j or i == j:
TC[i][j] = True
else:
TC[i][j] = False
for vertex k in 1..V:
# Invariant: TC[i][j] corresponds to the existence of path from i to j considering the intermediate vertices 1 to k-1
for vertex i in 1..V:
for vertex j in 1..V:
TC[i][j] = TC[i][j] or (TC[i][k] and TC[k][j])
Time Complexity:
O(V3)
Space Complexity:
O(V2)
Summary
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Take home message
Dijkstra’s algorithm works only for graphs with non-negative weights
Bellman-Ford computes shortest paths in graphs with negative weights in O(VE) and can also detect the negative cycles that are reachable
Floyd-Warshall Algorithm computes all-pairs shortest paths and transitive closure in O(V3)
Things to do (this list is not exhaustive)
Go through recommended reading and make sure you understand why the algorithms are correct
Implement Bellman-Ford and Floyd-Warshall Algorithms
Coming Up Next
Minimum spanning trees
Floyd-Warshall Algorithm: Correctness
FIT2004, Lec-9: Bellman-Ford and Floyd-Warshall Algorithms
Invariant: dist[i][j] corresponds to the shortest path from i to j considering only intermediate vertices 1 to k-1
What is the shortest distance from i to j considering only intermediate vertices 1-3 (e.g., k = 4)
13 (i 2 3 j)
What is the shortest distance from i to 4 considering only intermediate vertices 1-3 (e.g., k =4)
9 (i 1 4)
Base Case (k=1):
It is true because dist[][] is initialized based only on the adjacent edges
Inductive Step (example k = 4):
Assume dist[i][j] is the shortest path from i to j considering only vertices 1 to k-1
If k-th vertex is to improve on the known path from i to j, it can only be by going from i to k and then k to j (possibly via vertices in 1 to k-1)
Thus, minimum of dist(ikj) and dist(ij) gives the minimum distance from i to j considering the intermediate vertices 1 to k-1.
i
j
1
2
3
4
5
5
5
4
5
3
16
4
3
6
3
1
/docProps/thumbnail.jpeg