All pair shortest path by Sania Nisar

Analysis and Design of Algorithm. Floyd warshall algorithm , Floyd warshall Pseudocode , Jhonson's algorithm ,all pair shortest path ,single pair shortest path ,single source shortest path ,single destination shortest path ,time complexities , bellman–ford algorithm , dijkstra's algorithm.

1. MADE BY SANIA NISAR ALL PAIR SHORTEST PATH

2. Shortest Path Problem   In data structures, Shortest path problem is a problem of finding the shortest path(s) between vertices of a given graph. Shortest path between two vertices is a path that has the least cost as compared to all other existing paths. Shortest Path Algorithms   Shortest path algorithms are a family of algorithms used for solving the shortest path problem.  

3. Types of Shortest Path Problem Various types of shortest path problem are S Single-pair shortest path problem. Single-source shortest path problem. Single-destination shortest path problem. All pairs shortest path problem.

4. Single-Pair Shortest Path Problem   It is a shortest path problem where the shortest path between a given pair of vertices is computed.   Single-Source Shortest Path Problem   It is a shortest path problem where the shortest path from a given source vertex to all other remaining vertices is computed. Dijkstra’s Algorithm and Bellman Ford Algorithm are the famous algorithms used for solving single-source shortest path problem.

5. Single-Destination Shortest Path Problem   It is a shortest path problem where the shortest path from all the vertices to a single destination vertex is computed. By reversing the direction of each edge in the graph, this problem reduces to single-source shortest path problem. Dijkstra’s Algorithm is a famous algorithm adapted for solving single-destination shortest path problem.   All Pairs Shortest Path Problem   It is a shortest path problem where the shortest path between every pair of vertices is computed. Floyd- Warshall Algorithm and Johnson’s Algorithm are the famous algorithms used for solving All pairs shortest path problem .

6. Some Algorithms When no negative edges Using Dijkstra’s algorithm: O( V 3 ) Using Binary heap implementation: O(VE lg V) Using Fibonacci heap: O(VE + V 2 log V) When no negative cycles Floyd- Warshall : O( V 3 ) time When negative cycles Using Bellman-Ford algorithm: O( V 2 E) = O( V 4 ) Johnson : O(VE + V 2 log V) time based on a clever combination of Bellman-Ford and Dijkstra

7. Floyd- Warshall Algorithm It is used to solve All Pairs Shortest Path Problem. It computes the shortest path between every pair of vertices of the given graph. Floyd- Warshall Algorithm is an example of dynamic programming approach.

8. Advantages   Floyd- Warshall Algorithm has the following main advantages It is extremely simple. It is easy to implement.

9. Floyd- Warshall Psuedocode n = W . rows D = W for k = 1 to n for i = 1 to n for j = 1 to n return D

10. Time Complexity   Floyd- Warshall Algorithm consists of three loops over all the nodes. The inner most loop consists of only constant complexity operations. Hence, the asymptotic complexity of Floyd- Warshall algorithm is O(n 3 ). Here, n is the number of nodes in the given graph.

11. When Floyd- Warshall Algorithm is Used?   Floyd- Warshall Algorithm is best suited for dense graphs. This is because its complexity depends only on the number of vertices in the given graph. For sparse graphs, Johnson’s Algorithm is more suitable.  

12. Johnson’s Algorithm Johnson's algorithm  is a way to find the  shortest paths  between  all pairs of vertices  in an  edge-weighted ,  directed graph . It allows some of the edge weights to be  negative numbers , but no negative-weight  cycles  may exist.It turns all negative values into non-negative. It works by using the  Bellman–Ford algorithm  to compute a transformation of the input graph that removes all negative weights, allowing  Dijkstra's algorithm  to be used on the transformed graph.

13. Algorithm description Johnson's algorithm consists of the following steps: First, a new  node   s  is added to the graph, connected by zero-weight  edges  to each of the other nodes. Second, the  Bellman–Ford algorithm   is used, starting from the new vertex  s , to find for each vertex  v  the minimum weight  h ( v ) of a path from  s  to  v . If this step detects a negative cycle, the algorithm is terminated. Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm : an edge from u to v ,having length w( u,v ) , is given the new length  w ( u , v ) +  h ( u ) −  h ( v ). Finally,  s  is removed, and  Dijkstra's algorithm   is used to find the shortest paths from each node  s  to every other vertex in the reweighted graph.

14. Psuedocode Input : Graph G Output : List of all pair shortest paths for G Johnson(G){ G '.V = G.V + {n} G' .E = G.E + (( s,u ) for u in G.V) weight( n,u ) = in G.V Dist = BellmanFord (G ’.V , G’ .E) for edge( u,v ) in G '.E do weight( u,v ) += h[u] - h[v] End L = [] /*for storing result*/ for vertex v in G.V do L += Dijkstra(G, G.V) End return L }

15. Example | V | = 5 | E | = 9

16. Step : 1 Add source vertex to the given graph | V ’ | = 6 | E ’ | = 14

17. Step : 2 Find shortest path from “ S ” to all vertices. h ( a ) = δ ( s , a ) = 0 h ( b ) = δ ( s , b ) = s  d  c  b = 0 – 5 + 4 = -1 h ( c ) = δ ( s , c ) = s  d  c = 0 – 5 = -5 h ( d ) = δ ( s , d ) = s  d = h ( e ) = δ ( s , e ) = s  a  e = 0 – 4 = -4 h ( a ) h ( b ) -1 h ( c ) -5 h ( d ) h ( e ) -4

18. Step : 3 Find W ’ Formula for re-weighting edges W’ ( u , v ) = W ( u , v ) + h ( u ) – h ( v ) Re-weight all vertices using this formula. After re-weighting we got non-negative values.

19. W’( a , b )=W( a , b ) + h( a ) – h( b ) = 3 + 0 – (-1)= 4 W’( a , c )=W( a , c ) + h( a ) – h( c ) = 8 + 0 – (-5)= 13 W’( a , e )=W( a , e ) + h( a ) – h( e ) = -4 + 0 – (-4)= 0 W’( b , d )=W( b , d ) + h( b ) – h( d ) = 1 + (-1) – 0= 0 W’( b , e )=W( b , e ) + h( b ) – h( e ) = 7 + (-1) – (-4)= 10 W’( c , b )=W( c , b ) + h( c ) – h( b ) = 4 + (-5) – (-1)= 0 W’( d , c )=W( d , c ) + h( d ) – h( c ) = -5 + 0 – (-5)= 0 h ( a ) h ( b ) -1 h ( c ) -5 h ( d ) h ( e ) -4

20. W’( d , a )=W( d , a ) + h( d ) – h( a ) = 2 + 0 – 0= 2 W’( e , d )=W( e , d ) + h( e ) – h( d ) = 6 + (-4) – 0= 2 W’( s , a )=W( s , a ) + h( s ) – h( a ) = 0 + 0 – 0= 0 W’( s , b )=W( s , b ) + h( s ) – h( b ) = 0 + 0 – (-1)= 1 W’( s , c )=W( s , c ) + h( s ) – h( c ) = 0 + 0 – (-5)= 5 W’( s , d )=W( s , d ) + h( s ) – h( d ) = 0 + 0 – 0= 0 W’( s , e )=W( s , e ) + h( s ) – h( e ) = 0 + 0 – (-4)= 4 h ( a ) h ( b ) -1 h ( c ) -5 h ( d ) h ( e ) -4

21. Step : 4 Put new values of edges in the graph.

22. Step : 5 Remove source

23. Step : 6 Now find shortest distance from each vertex to every other vertex in the graph. Applying Dijkstra Algorithm. For Vertex A : δ ’( a , a )= δ ’( a , b )=0+2+0+0= 2 δ ’( a , c )=0+2+0= 2 δ ’( a , d )=0+2= 2 δ ’( a , e )=

24. To find “ δ ” δ ( u , v ) = δ ’( u, v ) – h( u ) + h( v ) For Vertex A : δ ( a ,a ) = δ ’( a , a ) – h( a ) + h( a ) = 0 – 0 + 0 = 0 δ ( a ,b ) = δ ’( a , b ) – h( a ) + h( b ) = 2 – 0 + (-1) = 1 δ ( a ,c ) = δ ’( a , c ) – h( a ) + h( c ) = 2 – 0 + (-5) = -3 δ ( a ,d ) = δ ’( a , d ) – h( a ) + h( d ) = 2 – 0 + 0 = 2 δ ( a ,e ) = δ ’( a , e ) – h( a ) + h( e ) = 0 – 0 + (-4) = -4 δ ’( a , a ) h ( a ) δ ’( a , b ) 2 h ( b ) -1 δ ’( a , c ) 2 h ( c ) -5 δ ’( a , d ) 2 h ( d ) δ ’( a , e ) h ( e ) -4

25. Shortest path from vertex A to every other vertex

26. For Vertex B : δ ’( b , a )= 0+2 = 2 δ ’( b , b )= δ ’( b , c )= 0+0 = δ ’( b , d )= δ ’( b , e )= 0+2+0= 2

27. To find “ δ ” δ ( u , v ) = δ ’( u, v ) – h( u ) + h( v ) For Vertex B : δ ( b ,a ) = δ ’( b , a ) – h( b ) + h( a ) = 2 – (-1) + 0 = 3 δ ( b ,b ) = δ ’( b , b ) – h( b ) + h( b ) = 0 – (-1) + (-1) = 0 δ ( b ,c ) = δ ’( b , c ) – h( b ) + h( c ) = 0 – (-1) + (-5) = -4 δ ( b ,d ) = δ ’( b , d ) – h( b ) + h( d ) = 0 – (-1) + 0 = 1 δ ( b ,e ) = δ ’( b , e ) – h( b ) + h( e ) = 2 – (-1) + (-4) = -1 δ ’( b , a ) 2 h ( a ) δ ’( b , b ) h ( b ) -1 δ ’( b , c ) h ( c ) -5 δ ’( b , d ) h ( d ) δ ’( b , e ) 2 h ( e ) -4

28. Shortest path from vertex B to every other vertex

29. For Vertex C : δ ’( c , a )= 0+0+2 = 2 δ ’( c , b )= δ ’( c , c )= δ ’( c , d )= 0+0= δ ’( c , e )= 0+0+2+0= 2

30. To find “ δ ” δ ( u , v ) = δ ’( u, v ) – h( u ) + h( v ) For Vertex C : δ ( c ,a ) = δ ’( c , a ) – h( c ) + h( a ) = 2 – (-5) + 0 = 7 δ ( c ,b ) = δ ’( c , b ) – h( c ) + h( b ) = 0 – (-5) + (-1) = 4 δ ( c ,c ) = δ ’( c , c ) – h( c ) + h( c ) = 0 – (-5) + (-5) = 0 δ ( c ,d ) = δ ’( c , d ) – h( c ) + h( d ) = 0 – (-5) + 0 = 5 δ ( c ,e ) = δ ’( c , e ) – h( c ) + h( e ) = 2 – (-5) + (-4) = 3 δ ’( c , a ) 2 h ( a ) δ ’( c , b ) h ( b ) -1 δ ’( c , c ) h ( c ) -5 δ ’( c , d ) h ( d ) δ ’( c , e ) 2 h ( e ) -4

31. Shortest path from vertex C to every other vertex

32. For Vertex D : δ ’( d , a )= 2 δ ’( d , b )= 0+0= δ ’( d , c )= δ ’( d , d )= δ ’( d , e )= 2+0= 2

33. To find “ δ ” δ ( u , v ) = δ ’( u, v ) – h( u ) + h( v ) For Vertex D : δ ( d ,a ) = δ ’( d , a ) – h( d ) + h( a ) = 2 – 0 + 0 = 2 δ ( d ,b ) = δ ’( d , b ) – h( d ) + h( b ) = 0 – 0 + (-1) = -1 δ ( d ,c ) = δ ’( d , c ) – h( d ) + h( c ) = 0 – 0 + (-5) = -5 δ ( d ,d ) = δ ’( d , d ) – h( d ) + h( d ) = 0 – 0 + 0 = 0 δ ( d ,e ) = δ ’( d , e ) – h( d ) + h( e ) = 2 – 0 + (-4) = -2 δ ’( d , a ) 2 h ( a ) δ ’( d , b ) h ( b ) -1 δ ’( d , c ) h ( c ) -5 δ ’( d , d ) h ( d ) δ ’( d , e ) 2 h ( e ) -4

34. Shortest path from vertex D to every other vertex

35. For Vertex E : δ ’( e , a )= 2+2= 4 δ ’( e , b )= 2+0+0= 2 δ ’( e , c )= 2+0= 2 δ ’( e , d )= 2 δ ’( e , e )=

36. To find “ δ ” δ ( u , v ) = δ ’( u, v ) – h( u ) + h( v ) For Vertex E : δ ( e ,a ) = δ ’( e , a ) – h( e ) + h( a ) = 2 – 0 + 0 = 2 δ ( e ,b ) = δ ’( e , b ) – h( e ) + h( b ) = 0 – 0 + (-1) = -1 δ ( e ,c ) = δ ’( e , c ) – h( e ) + h( c ) = 0 – 0 + (-5) = -5 δ ( e ,d ) = δ ’( e , d ) – h( e ) + h( d ) = 0 – 0 + 0 = 0 δ ( e ,e ) = δ ’( e , e ) – h( e ) + h( e ) = 2 – 0 + (-4) = -2 δ ’( e , a ) 4 h ( a ) δ ’( e , b ) 2 h ( b ) -1 δ ’( e , c ) 2 h ( c ) -5 δ ’( e , d ) 2 h ( d ) δ ’( e , e ) h ( e ) -4

37. Shortest path from vertex E to every other vertex

38. Time Complexity:  The main steps in algorithm are Bellman Ford Algorithm called once and Dijkstra called V times. Time complexity of Bellman Ford is O(VE) and time complexity of Dijkstra is O( VLogV ). So overall time complexity is O(V 2 log V + VE). But for sparse graphs, the algorithm performs much better than  Floyd Warshell .