Space complexity: O(n^3), O(n^2)

In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshall's algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time.

//Floyd-Warshall

//All-pairs Shortest Path

void floyd_warshall() {

for(int k=1;k<=n;k++) {

for(int i=1;i<=n;i++) {

for(int j=1;j<=n;j++) {

d[i][j][k]=(d[i][j][k-1] < d[i][k][k-1]+d[k][j][k-1]

? d[i][j][k-1]

: d[i][k][k-1]+d[k][j][k-1]);

}

}

}

}

Another version with space complexity O(n^2)

//simple version

// range from 0 to n-1

extern d[i][j]

void floyd_warshall() {

for(int k=0;k for(int i=0;i for(int j=0;j if(d[i][j] > d[i][k]+d[k][j])

d[i][j]=d[i][k]+d[k][j];

}

}

}

}

I don't know exactly what is variable k used for?

ReplyDeleteVariable k is like a stage. The value d[i][j][k] for each stage k is calculated from stage k-1. This is more obvious in the upper O(n^3) space complexity example.

ReplyDelete