Monday 21 January 2013

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(n3) 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. 

No comments:

Post a Comment