算法课件Lecture10章节.pptVIP

All –pairs shortest paths problem Problem: Given a directed graph G=(V, E), and a weight function w: E?R, for each pair of vertices u, v, compute the shortest path weight ?(u, v), and a shortest path if exists. Output: a V?V matrix D=(dij), where, dij contains the weight of a shortest path from vertex i to vertex j. Methods Application of single source shortest path algorithms Direct methods to solve the problem: Matrix multiplication Floyd-Warshall algorithm Johnson’s algorithm for sparse graphs Transitive closure (Floyd-Warshall algorithm) Motivation Computer network Aircraft network (e.g. flying time, fares) Railroad network Table of distances between all pairs of cities for a road atlas Single source shortest path algorithms If edges are non-negative: Running the Dijkstra’s algorithm n-times, once for each vertex as the source running time: O(V2 lgV+VE) //using Fibonacci-heap Single source shortest path algorithms Negative-weight edges: Bellman-Ford algorithm Running time: O(V2 E) Data structure Adjacency matrix w: E ? ? as V x V matrix W 0 if i = j, wij = weight of edge (i,j) if i ≠ j and (i,j) ? E, ∞ if i ≠ j and (i,j) ? E Matrix multiplication (idea) lij(m) : minimum weight of any path from i to j that contains at most m edges Matrix multiplication (idea) Matrix multiplication (idea) lij(m) = min (lij(m-1), min1≤k≤n {lik(m-1) + wkj}) look at all possible predecessors k of j and compare Matrix multiplication (structure) lij(1) = wij lij(m) = min (lij(m-1), min1≤k≤n {lik(m-1) + wkj}) = = min1≤k≤n {lik(m-1) + wkj} Matrix multiplication (structure) Compute a series of matrices L(1), L(2), …, L(n-1) L(m) = L(m-1) ? W Final matrix L(n-1) contains the final shortest-path weights Matrix multiplication (pseudo-code) Matrix multiplication (example) Matrix multiplication (example) matrix multiplication (example) matrix multiplication (example) matrix multiplication (example) ? 1