Floyd-Warshall All-Pairs Shortest Path

Time complexity: O(n^3)
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];
			}
		}
	}
}