程序代写代做代考 algorithm data structure PowerPoint Presentation

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 in the whole graph:
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 in the whole graph:
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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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) ij 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(ij) Update/create shortcut i j with weight equal to dist(ikj) 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(ikj) and dist(ij) 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(ikj) and dist(ij) 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(ikj) and dist(ij) 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