「算法」最短路径—Floyd弗洛伊德算法

多源最短路径：两点之间的最短路径。

二维矩阵，存放地点之间距离。

从4—>3，如果经过1的话，路径是11，比12短。e[4][3]>e[4][1]+e[1][3]

所以我们可以假设，如果两点间只允许经过1，那么最短路径应该如何计算？

判断e[i][j]是否大于e[i][1]+e[1][j]，如果大于，则使e[i][j]=e[i][1]+e[1][j]

我们对每个点都扫描一遍。（默认定义无穷为9999,通常设为99999999）

for(i=1;i<=n;i++)
{
 for(j=1;j<=n;j++)
 {
 if(e[i][1]<9999 && e[1][j]<9999 && e[i][j]>e[i][1]+e[1][j])
 e[i][j]=e[i][1]+e[1][j];
 }
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

扫描完必经过1的，就该继续扫描必经过2的。

欢迎大家来到IT世界,在知识的湖畔探索吧!for(i=1;i<=n;i++)
{
 for(j=1;j<=n;j++)
 {
 if(e[i][2]<9999 && e[2][j]<9999 && e[i][j]>e[i][2]+e[2][j])
 e[i][j]=e[i][2]+e[2][j];
 }
}

所以我们整理一下：

for(k=1;k<=n;k++)
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 if(e[i][k]<9999 && e[k][j]<9999 && e[i][j]>e[i][k]+e[k][j])
 e[i][j]=e[i][k]+e[k][j];

输出最短路径：

欢迎大家来到IT世界,在知识的湖畔探索吧!printf("%d",e[i][j]);