算法分析与实践-作业2-1采用Floyd算法求解各个顶点的最短距离

Floyd算法求解各个顶点的最短距离

1、问题

2、解析

可以先用一个二维数组a来表示各顶点之间的最短距离矩阵如下图所示，例如点2无法到达点1，则距离a[2][1]为∞，自己到自己如a[1][1]则距离为0；

经过观察发现，点4到点3还可以先经过点1，那么距离为a[4][1]+a[1][3]=5+6=11，比12小，所以每个顶点都有可能使得另外两个顶点之间的距离变短。
那么先引入点1，使得其他点能经过点1再到目标点，要使得距离比原来短，那么只需判断a[i][1]+a[1][j]是否比a[i][j]要小即可。
即：

这一小部分的实现代码为：

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

那么同理，在引入点1的基础上，引入点2：

在引入点1、点2的基础上，引入点3：

在引入点1、点2、点3的基础上，引入点4，最后完成：

3、设计

核心部分为顶点的引入以及比较最短路径的过程：

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