**All Pairs Shortest Path Problem **

- Let G be a directed graph with n vertices and cost be its adjacency matrix
- The problem is to determine a matrix A such that
**A(i,j)**is the length of a shortest path from**i**vertex to^{th}**j**vertex^{th } - This problem is equivalent to solving
**n**single source shortest path problems using greedy method - Robert Floyd developed a solution using dynamic programming method
- A shortest path from I to j goes through 0 or more intermediate vertices and terminates at j
- If k is an intermediate vertex on this shortest path, then the sub paths from i to k and from
**k**to**j**must be shortest paths from i to k and k to j respectively. This is based on the principle of optimality. - The solution matrix is obtained iteration wise by computing
**A**_{0, }A_{1,}A_{2,}… A_{n}

**A**is the cost matrix. The next iterations give the matrix_{0 }**A**which is computed as follows:_{k }

*A*(^{k}*i*,*j*) = min{*A*^{k-}^{1}(*i*,*j*),*A*^{k-}^{1}(*i*,*k*) +*A*^{k-}^{1}(*k*,*j*) },*k >=*1 - An algorithm for the all-pairs shortest path problem is given below:
Algorithm AllPaths(cost, A, n) // cost[1:n][1:n] is the cost adjacency matrix of a graph with n vertices; // A[i][j] is the cost of a shortest path from vertex i to vertex j. // cost[i][i] = 0.0, for 1 <= i <= n. { for ( i:=1 to n ) do { for ( j:=1 to n ) do { A[i][j] := cost[i][j]; // Copy cost into A. } } for ( k:=1 to n ) do { for ( i:=1 to n ) do { for ( j:=1 to n ) do { A[i][j] = min(A[i][j], A[i][k]+A[k][j]); } } } }

**Time complexity of Floyd Warshall Algorithm****is O(n**^{3})

Topic : All Pairs Shortest Path Problem | Floyd Warshall Algorithm

** **