弗洛伊德算法求最短路径（C语言详解）

通过前一节对迪杰斯特拉算法的学习，主要解决从网（带权图）中某一顶点计算到其它顶点之间的最短路径问题。如果求有向网中每一对顶点之间的最短路径，使用迪杰斯特拉算法的解决思路是：以每一个顶点为源点，执行迪杰斯特拉算法。这样可以求得每一对顶点之间的最短路径。

本节介绍另外一种解决算法，也就是弗洛伊德算法，该算法相比于使用迪杰斯特拉算法在解决此问题上的时间复杂度虽然相同，都为 O(n³)，但是弗洛伊德算法的实现形式更简单。

弗洛伊德的核心思想是：对于网中的任意两个顶点（例如顶点 A 到顶点 B）来说，之间的最短路径不外乎有 2 种情况：

1. 直接从顶点 A 到顶点 B 的弧的权值为顶点 A 到顶点 B 的最短路径；
2. 从顶点 A 开始，经过若干个顶点，最终达到顶点 B，期间经过的弧的权值和为顶点 A 到顶点 B 的最短路径。

所以，弗洛伊德算法的核心为：对于从顶点 A 到顶点 B 的最短路径，拿出网中所有的顶点进行如下判断：

其中，K 表示网中所有的顶点；Dis（A，B） 表示顶点 A 到顶点 B 的距离。

也就是说，拿出所有的顶点 K，判断经过顶点 K 是否存在一条可行路径比直达的路径的权值小，如果式子成立，说明确实存在一条权值更小的路径，此时只需要更新记录的权值和即可。

任意的两个顶点全部做以上的判断，最终遍历完成后记录的最终的权值即为对应顶点之间的最短路径。

图 1 带权图

举个例子，在使用弗洛伊德算法计算图 1 中的任意两个顶点之间的最短路径时，具体实施步骤为：

首先，记录顶点之间初始的权值，如下表所示：

 

依次遍历所有的顶点，假设从 V0 开始，将 V0 作为中间点，看每对顶点之间的距离值是否会更小。最终 V0 对于每对顶点之间的距离没有任何改善。

对于 V0 来说，由于该顶点只有出度，没有入度，所以没有作为中间点的可能。同理，V1也没有可能。

将 V2 作为每对顶点的中间点，有影响的为 （V0，V3） 和 （V1，V3）：

例如，（V0，V3）权值为无穷大，而（V0，V2）+（V2，V3）= 60，比之前的值小，相比而言后者的路径更短；同理 （V1，V3）也是如此。

更新的表格为：

以 V3 作为中间顶点遍历各队顶点，更新后的表格为：

以 V4 作为中间顶点遍历各队顶点，更新后的表格为：

而对于顶点 V5 来说，和顶点 V0 和 V1 相类似，所不同的是，V5 只有入度，没有出度，所以对各队顶点的距离不会产生影响。最终采用弗洛伊德算法求得的各个顶点之间的最短路径如上图所示。

弗洛伊德算法的具体实现

#include <stdio.h>
#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示弧的权值的类型
#define VertexType int                      //图中顶点的数据类型
#define INFINITY 65535
typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    VRType arcs[MAX_VERtEX_NUM][MAX_VERtEX_NUM];                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}MGraph;
typedef int PathMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];     //用于存储最短路径中经过的顶点的下标
typedef int ShortPathTable[MAX_VERtEX_NUM][MAX_VERtEX_NUM]; //用于存储各个最短路径的权值和
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,VertexType v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; i<G->vexnum; i++) {
        if (G->vexs[i]==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i>G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造有向网
void CreateUDG(MGraph *G){
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j]=INFINITY;
        }
    }
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2,w;
        scanf("%d,%d,%d",&v1,&v2,&w);
        int n=LocateVex(G, v1);
        int m=LocateVex(G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m]=w;
    }
}
//弗洛伊德算法，其中P二维数组存放各对顶点的最短路径经过的顶点，D二维数组存储各个顶点之间的权值
void ShortestPath_Floyed(MGraph G,PathMatrix *P,ShortPathTable *D){
    //对P数组和D数组进行初始化
    for (int v=0; v<G.vexnum; v++) {
        for (int w=0; w<G.vexnum; w++) {
            (*D)[v][w]=G.arcs[v][w];
            (*P)[v][w]=-1;
        }
    }
    //拿出每个顶点作为遍历条件
    for (int k=0; k<G.vexnum; k++) {
        //对于第k个顶点来说，遍历网中任意两个顶点，判断间接的距离是否更短
        for (int v=0; v<G.vexnum; v++) {
            for (int w=0; w<G.vexnum; w++) {
                //判断经过顶点k的距离是否更短，如果判断成立，则存储距离更短的路径
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    (*D)[v][w]=(*D)[v][k] + (*D)[k][w];
                    (*P)[v][w]=k;
                }
            }
        }
    }
}
int main(){
    MGraph G;
    CreateUDG(&G);
    PathMatrix P;
    ShortPathTable D;
    ShortestPath_Floyed(G, &P, &D);
    for (int i=0; i<G.vexnum; i++) {
        for (int j=0; j<G.vexnum; j++) {
            printf("%d ",P[i][j]);
        }
        printf("\n");
    }
    for (int i=0; i<G.vexnum; i++) {
        for (int j=0; j<G.vexnum; j++) {
            printf("%d ",D[i][j]);
        }
        printf("\n");
    }
    return 0;
}

运行结果为（以图 1 为例）

其中，输出结果中 65535 表示该位置所表示的两顶点之间的距离为无穷大。