（转）最短路径Floyd算法

本文转自：https://blog.csdn.net/jack_20/article/details/78031310

Floyd算法求所有顶点到所有顶点的最短路径，时间复杂度也为O(n^3)，但其算法非常简洁优雅。为了能讲明白该算法的精妙所在，先来看最简单的案例。

下图左部分是一个最简单的3个顶点连通网图。

 

先定义两个数组D[3][3]和P[3][3]，D代表顶点到顶点的最短路径权值和的矩阵，P代表对应顶点的最小路径的前驱矩阵。在未分析任何顶点之前，我们将D命

名为D-1  ，其实它就是初始的图的邻接矩阵。将P命名为P-1 ，初始化为图中所示的矩阵。首先，我们来分析，所有的顶点经过v0后到达另一顶点的最短距离。

因为只有三个顶点，因此需要查看v1->v0->v2，得到D-1 [1][0] + D-1 [0][2] = 2 + 1 = 3。D-1 [1][2]表示的是v1->v2的权值是5，我们发现

D-1 [1][2] > D-1 [1][0] + D-1 [0][2]，通俗的讲就是v1->v0->v2比直接v1->v2距离还要近。所以我们就让D-1 [1][2]  = D-1 [1][0] + D-1 [0][2]，同样的D-1 [2][1]  = 3，

于是就有了D0 的矩阵。因为有了变化，所以P矩阵对应的P-1[1][2]和P-1[2][1]也修改为当前中转的顶点v0的下标0，于是就有了P0。也就是说：

 --->动态规划乎

接下来，其实也就是在D0和P0的基础上，继续处理所有顶点经过v1和v2后到达另一顶点的最短路径，得到D1和P1、D2和P2完成所有顶点到所有顶点的最短

路径的计算。首先我们针对下图的左网图准备两个矩阵D-1和P-1，就是网图的邻接矩阵，初设为P[j][j] = j这样的矩阵，它主要用来存储路径。

 

具体代码如下，注意是：求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。

/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */

void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
    int v,w,k;
    /* 初始化D与P */
    for(v=0; v<G.numVertexes; ++v)            
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            /* D[v][w]值即为对应点间的权值 */
            (*D)[v][w]=G.arc[v][w]; 
            /* 初始化P */           
            (*P)[v][w]=w;                    
        }
    }
    for(k=0; k<G.numVertexes; ++k)
    {
        for(v=0; v<G.numVertexes; ++v)
        {
            for(w=0; w<G.numVertexes; ++w)
            {
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    /* 将当前两点间权值设为更小的一个 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];    
                    /* 路径设置为经过下标为k的顶点 */
                    (*P)[v][w]=(*P)[v][k];                
                }
            }
        }
    }
}

下面介绍下详细的执行过程：

（1）程序开始运行，第4-11行就是初始化了D和P，使得它们成为 上图 的两个矩阵。从矩阵也得到，v0->v1路径权值为1，v0->v2路径权值为5，

v0->v3无边连线，所以路径权值为极大值65535。

（2）第12~25行，是算法的主循环，一共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。

（3）当k = 0时，也就是所有的顶点都经过v0中转，计算是否有最短路径的变化。可惜结果是，没有任何变化，如下图所示。

 

（4）当k = 1时，也就是所有的顶点都经过v1中转。此时，当v = 0 时，原本D[0][2] = 5，现在由于D[0][1] + D[1][2] = 4。因此由代码的的第20行，

二者取其最小值，得到D[0][2] = 4，同理可得D[0][3] = 8、D[0][4] = 6，当v = 2、3、4时，也修改了一些数据，请看下图左图中虚线框数据。

由于这些最小权值的修正，所以在路径矩阵P上，也要做处理，将它们都改为当前的P[v][k]值，见代码第21行。

 

（5）接下来就是k = 2，一直到8结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D0是以D-1为基础，D1是以D0为基础，

......，D8是以D7为基础的。最终，当k = 8时，两个矩阵数据如下图所示。

 

至此，我们的最短路径就算是完成了。可以看到矩阵第v0行的数值与迪杰斯特拉算法求得的D数组的数值是完全相同。而且这里是所有顶点到所有

顶点的最短路径权值和都可以计算出。

那么如何由P这个路径数组得出具体的最短路径呢？以v0到v8为例，从上图的右图第v8列，P[0][8]= 1，得到要经过顶点v1，然后将1取代0，得到P[1][8] = 2，

说明要经过v2，然后2取代1得到P[2][8] = 4，说明要经过v4，然后4取代2，得到P[4][8]= 3，说明要经过3，........，这样很容易就推倒出最终的最短路径值为

v0->v1->v2->v4->v3->v6->v7->v8。

求最短路径的显示代码可以这样写：

for(v=0; v<G.numVertexes; ++v)
{
        for(w=v+1; w<G.numVertexes; w++)
        {
            printf("v%d-v%d weight: %d ",v,w,D[v][w]);
            k=P[v][w];                /* 获得第一个路径顶点下标 */
            printf(" path: %d",v);    /* 打印源点 */
            while(k!=w)                /* 如果路径顶点下标不是终点 */
            {
                printf(" -> %d",k);    /* 打印路径顶点 */
                k=P[k][w];            /* 获得下一个路径顶点下标 */
            }
            printf(" -> %d\n",w);    /* 打印终点 */
        }
        printf("\n");
}

总体的代码如下：

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* 构件图 */
void CreateMGraph(MGraph *G)
{
    int i, j;
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=16;
    G->numVertexes=9;
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        G->vexs[i]=i;
    }
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITY;
        }
    }
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    G->arc[7][8]=4;
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
}

/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
    int v,w,k;
    for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            (*D)[v][w]=G.arc[v][w];    /* D[v][w]值即为对应点间的权值 */
            (*P)[v][w]=w;                /* 初始化P */
        }
    }
    for(k=0; k<G.numVertexes; ++k)
    {
        for(v=0; v<G.numVertexes; ++v)
        {
            for(w=0; w<G.numVertexes; ++w)
            {
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {/* 如果经过下标为k顶点路径比原两点间路径更短 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */
                    (*P)[v][w]=(*P)[v][k];/* 路径设置为经过下标为k的顶点 */
                }
            }
        }
    }
}
int main(void)
{
    int v,w,k;
    MGraph G;
    Patharc P;
    ShortPathTable D; /* 求某点到其余各点的最短路径 */
    CreateMGraph(&G);
    ShortestPath_Floyd(G,&P,&D);
    printf("各顶点间最短路径如下:\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=v+1; w<G.numVertexes; w++)
        {
            printf("v%d-v%d weight: %d ",v,w,D[v][w]);
            k=P[v][w];                /* 获得第一个路径顶点下标 */
            printf(" path: %d",v);    /* 打印源点 */
            while(k!=w)                /* 如果路径顶点下标不是终点 */
            {
                printf(" -> %d",k);    /* 打印路径顶点 */
                k=P[k][w];            /* 获得下一个路径顶点下标 */
            }
            printf(" -> %d\n",w);    /* 打印终点 */
        }
        printf("\n");
    }
    printf("最短路径D\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d\t",D[v][w]);
        }
        printf("\n");
    }
    printf("最短路径P\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d ",P[v][w]);
        }
        printf("\n");
    }
    return 0;
}