最短路径算法：Floyd、判断两点是否连通

d[i][j]表示从点i到点j之间的最短路径
d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
d[i][j]=G[i][j],如果不联通是正无穷

for(int i=1;i<=k;i++){ //中转点
	//d[i][j]以前k-1个点作为中转点的最短路径
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
		}
	}
	//d[i][j]以前k个点作为中转点的最短路径
}

最短路径算法：Floyd、判断两点是否连通

原文：https://www.cnblogs.com/ictiger/p/14824664.html