All pair shortest path algorithm with example pdf

all pair shortest path floyd warshall algorithm example all pair shortest path using dynamic programming in c
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures All-pairs shortest path Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.All-pairs Shortest Path 2 Outline This topic will: – Review Dijkstra’s algorithm for finding a shortest path – Consider what happens if we want to find all shortest paths – We will look at the Floyd-Warshall algorithm for: • Finding these shortest distances • Finding the paths corresponding to these distances – We conclude by finding the transitive closureAll-pairs Shortest Path 3 5.1 Background Dijkstra’s algorithm finds the shortest path between two nodes 2 – Run time:  V  If we wanted to find the shortest path between all pairs of nodes, we could apply Dijkstra’s algorithm to each vertex: – Run time:  V E ln V  2 3 EV  In the worst case, if , the run time is VV ln  All-pairs Shortest Path 4 5.1 Background Any algorithm that finds the shortest path between all pairs must consider, each pair of vertices; therefore, a lower bound on the execution would be 2  V  Now, Dijkstra’s algorithm has the following run times: – Best case: 2 If EV  , running Dijkstra for each vertex is VV ln   – Worst case: 2 3 EV  If , running Dijkstra for each vertex isVV ln  All-pairs Shortest Path 5 5.1.1 Problem 3 o V ln V Question: for the worst case, can we find a algorithm?  We will look at the Floyd-Warshall algorithmAll-pairs Shortest Path 6 5.1.2 Strategy First, let’s consider only edges that connect vertices directly: 0 If ij   (0) d w If there is an edge from i to j  i,, j i j   Otherwise  Here, w is the weight of the edge connecting vertices i and j i,j (0) (0) dd – Note, this can be a directed graph; i.e., it may be that i,, j j i In C++, we would define a two-dimensional array double dnum_verticesnum_vertices;All-pairs Shortest Path 7 5.1.2 Strategy Consider this graph of seven vertices 0 0  – The edges defining the values d and d are highlighted 5,3 6,7All-pairs Shortest Path 8 5.1.2 Strategy Suppose now, we want to see whether or not the path going through vertex v is shorter than a direct edge? 1 0 0 0  d  d d – Is ? 5,3 5,1 1,3 0 0 0  – Is d  d d ? 6,7 6,1 1,7All-pairs Shortest Path 9 5.1.2 Strategy 1  Thus, for each pair of edges, we will define d by calculating: ij , 1 0 0 0  d min d ,d d  i, j i, j i,1 1, jAll-pairs Shortest Path 10 5.1.2 Strategy 10  10  dd Note that and ; thus, we need just run the dd ii ,1 ,1 1,jj 1, algorithm for each pair of vertices: for ( int i = 0; i num_vertices; ++i ) for ( int j = 0; j num_vertices; ++j ) dij = std::min( dij, di0 + d0j ); All-pairs Shortest Path 11 5.1.2 The General Step k1  Define d as the shortest distance, but only allowing intermediate ij , visits to vertices v , v , …, v 1 2 k–1 – Suppose we have an algorithm that has found these values for all pairsAll-pairs Shortest Path 12 5.1.2 The General Step k  How could we find d ; that is, the shortest path allowing ij , intermediate visits to vertices v , v , …, v , v ? 1 2 k–1 kAll-pairs Shortest Path 13 5.1.2 The General Step With v , v , …, v as intermediates, have assumed we have found 1 2 k–1 the shortest paths from v to v , v to v and v to v i j i k k j – The only possible shorter path including v would be the path from v to k i v continuing from there to v k j kk1k1k1 d min d ,d d Thus, we calculate  i, j i, j i,k k, jAll-pairs Shortest Path 14 5.1.2 The General Step Finding this for all pairs of vertices gives us all shortest paths from v to v possibly going through vertices v , v , …, v i j 1 2 k kk1 kk1  dd dd – Again, note that and do not change under this step k,, j k j i,, k i k – To simplify, the notation, we can remove the superscriptsAll-pairs Shortest Path 15 5.1.2 The General Step Thus, the calculation is straight forward: for ( int i = 0; i num_vertices; ++i ) for ( int j = 0; j num_vertices; ++j ) dij = std::min( dij, dik + dkj ); All-pairs Shortest Path 16 5.1.2 The Floyd-Warshall Algorithm Thus, we have found the Floyd-Warshall algorithm: double dnum_verticesnum_vertices; // Initialize the matrix d: Theta(V2) // ... // Run Floyd-Warshall for ( int k = 0; k num_vertices; ++k ) for ( int i = 0; i num_vertices; ++i ) for ( int j = 0; j num_vertices; ++j ) dij = std::min( dij, dik + dkj ); 3  V Run time? All-pairs Shortest Path 17 5.1.2 The Floyd-Warshall Algorithm Question: we’ve already argued that at step k, d and d remain i,k k,j unchanged, would you want to avoid the calculation if i = k or j = k? // Run Floyd-Warshall for ( int k = 0; k num_vertices; ++k ) for ( int i = 0; i num_vertices; ++i ) for ( int j = 0; j num_vertices; ++j ) if ( i = k && j = k ) dij = std::min( dij, dik + dkj ); Would you perform  V checks to avoid a operation?  1 All-pairs Shortest Path 18 5.1.2 The Floyd-Warshall Algorithm In such a case, if you must absolutely minimize the iterations: // Run Floyd-Warshall for ( int k = 0; k num_vertices; ++k ) for ( int i = 0; i k; ++i ) for ( int j = 0; j k; ++j ) dij = std::min( dij, dik + dkj ); for ( int j = k + 1; j num_vertices; ++j ) dij = std::min( dij, dik + dkj ); for ( int i = k + 1; i num_vertices; ++i ) for ( int j = 0; j k; ++j ) dij = std::min( dij, dik + dkj ); for ( int j = k + 1; j num_vertices; ++j ) dij = std::min( dij, dik + dkj ); All-pairs Shortest Path 19 Example Consider this graphAll-pairs Shortest Path 20 Example The adjacency matrix is 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  This would define our matrix D = (d ) ij