Floyd-Warshall Algorithm: C/C++ Program

  Floyd-Warshall algorithm (Also called Floyd's Algorithm) is used to solve the All-Pairs Shortest Path problem in Graphs. The Algorithm's time complexity is O(n³) for a graph with n nodes. The algorithm is given below.

for each vertex v

     dist[v][v] ← 0
for each edge (u,v)

     dist[u][v] ← w(u,v) 

for k from 1 to |V|       

     for i from 1 to |V|

         for j from 1 to |V|

                if dist[i][k] + dist[k][j] < dist[i][j] then   

                     dist[i][j] ← dist[i][k] + dist[k][j]  

  Floyd-Warshall algorithm is essentially same as Warshall's algorithm used to find the transitive closure of a relation R. Floyd-Warshall algorithm is an example for Dynamic Programming.

Click here to download the C Program implementing Floyd-Warshall Algorithm.   
Click here to download the C++ Program implementing Floyd-Warshall Algorithm.