算法:最短路径之弗洛伊德(Floyd)算法

为了能讲明白弗洛伊德(Floyd)算法的主要思想,我们先来看最简单的案例。图7-7-12的左图是一个简单的3个顶点的连通网图。

我们先定义两个二维数组D[3][3]和P[3][3], D代表顶点与顶点的最短路径权值和的矩阵。P代表对应顶点的最短路径的前驱矩阵。在未分析任何顶点之前,我们将D命名为D(-1),其实它就是初始图的邻接矩阵。将P命名为P(-1), 初始化为图中的矩阵。

首先我们来分析,所有的顶点经过v0后到达另一顶点的最短路径。因为只有3个顶点,因此需要查看v1->v0->v2,得到

D(-1)[1][0] + D(-1)[0][2] = 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] = 3, 同样地D(-1)[2][1] = 3, 于是就有了D(0)矩阵。因为有变化,所以P矩阵对应的P(-1)[1][2]和P(-1)[2][1]也修改为当前中转的顶点v0的下标0, 于是就有了P(0)。也就是说

接下来,也就是在D(0)和P(0)的基础上继续处理所有顶点经过v1和v2后到达另一顶点的最短路径,得到D(1)和P(1)、D(2)和P(2)完成所有顶点到所有顶点的最短路径计算工作。

首先我们针对图7-7-13的左网图准备两个矩阵D(-1)和P(-1),D(-1)就是网图的邻接矩阵,P(-1)初设为P[i][j]=j 这样的矩阵。主要用来存储路径。

代码如下(改编自《大话数据结构》):注意因为是要求所有顶点到所有顶点的最短路径,因为使用二维数组。

#include<iostream>
using namespace std;

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535

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 MG, Patharc P, ShortPathTable D)
{
    int v, w, k;
    for (v = 0; v < MG.numVertexes; v++)/* 初始化D与P */
    {
        for (w = 0; w < MG.numVertexes; w++)
        {
            D[v][w] = MG.arc[v][w];/* D[v][w]值即为对应点间的权值 */
            P[v][w] = w;/* 初始化P */
        }
    }

    for (k = 0; k < MG.numVertexes; k++)
    {
        for (v = 0; v < MG.numVertexes; v++)
        {
            for (w = 0; w < MG.numVertexes; w++)
            {
                /* 如果经过下标为k顶点路径比原两点间路径更短 */
                if (D[v][w] > D[v][k] + D[k][w])
                {
                    /* 将当前两点间权值设为更小的一个 */
                    D[v][w] = D[v][k] + D[k][w];
                    P[v][w] = P[v][k];/* 路径设置为经过下标为k的顶点 */
                }
            }
        }
    }
}

int main(void)
{
    int v, w, k;
    MGraph MG;
    Patharc P;
    ShortPathTable D;
    CreateMGraph(&MG);
    ShortestPath_Floyd(MG, P, D);

    cout << "各顶点间最短路径如下: " << endl;

    for (v = 0; v < MG.numVertexes; v++)
    {
        for (w = v + 1; w < MG.numVertexes; w++)
        {
            cout << "v" << v << "--" << "v" << w << " weight: " << D[v][w]
                 << " Path: " << v << ' ';
            k = P[v][w];
            while (k != w)
            {
                cout << "-> " << k << " ";
                k = P[k][w];
            }
            cout << "-> " << w << endl;
        }
        cout << endl;
    }

    return 0;
}

输出为:

程序中的算法代码非常简洁,即用了一个三层循环,k代表的是中转结点的下标,v代表起始结点,w代表结束终点。k = 0 ~ 8,表示针对每个顶点作为中转结点得到的计算结果,最终当k = 8时,两矩阵数据如图7-7-16所示。

从上图我们可以看到第v2行的数值与Dijkstra算法求得的D数组的数值完全一样,都是{4, 3, 0, 3, 1, 4, 6, 8, 12 }, 而且这里是所有顶点到所有顶点的最短路径权值和都可以计算得出。那么如何由P这个路径数组得出具体的最短路径呢?以v2到v8为例,P[2][8] = 4,说明要经过顶点v4, 将4替换2,P[4][8] = 3, 说明经过v3, ......., 最终推导出最短路径为:v2->v4->v3->v6->v7->v8。

Floyd算法使用了三层循环,故时间复杂度也为O(n^3),与Dijkstra算法一致,不过Floyd算法代码简洁,虽简洁但也不一定好懂,还是需要多加揣摩才能领会。另外,虽然我们使用的例子都是无向图的,但它们对于有向图依然有效,只不过在创建图的时候,有向图的邻接矩阵不是对称的而已。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

tarjan系列算法代码小结

个人使用,可能不是很详细 强联通分量 这里的dfn可以写成low 因为都是在栈中,只要保证该节点的low值不为本身即可 void tarjan(int now)...

3497
来自专栏Android点滴积累

Android高效内存2:让图片占用尽可能少的内存

Android高效内存:让图片占用尽可能少的内存 一、让你的图片最小化 1.1 大图小图内存使用情况对比 大图:440 * 336    小图:220 * 16...

25311
来自专栏猿人谷

跳台阶问题

题目: 给定一个有N个台阶的楼梯,一个人从下到上开始跳台阶,这个人有两种跳的方式:一次跳一个台阶,一次跳两个台阶; 问:从台阶底端跳到台阶顶端,有多少种跳台阶的...

1809
来自专栏Python小屋

Python两种方法求解登楼梯问题(京东2016笔试题)

问题:假设一段楼梯共15个台阶,小明一步最多能上3个台阶,那么小明上这段楼梯一共有多少种方法? 解析:从第15个台阶上往回看,有3种方法可以上来(从第14个台阶...

3819
来自专栏小特工作室

基于iTextSharp的PDF文档操作

  公司是跨境电商,需要和各种物流打交道,需要把东西交给物流,让他们发到世界各地。其中需要物流公司提供一个运单号,来追踪货物到达哪里?!   最近在和DHL物流...

22010
来自专栏数据结构与算法

点双连通分量与割点

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量 双连通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 点双连通分量 对于一个...

3598
来自专栏菩提树下的杨过

Flash/Flex学习笔记(51):3维旋转与透视变换(PerspectiveProjection)

Flash/Flex学习笔记(49):3D基础 里已经介绍了3D透视的基本原理,不过如果每次都要利用象该文中那样写一堆代码,估计很多人不喜欢,事实上AS3的Di...

1858
来自专栏calmound

ZOJ 3631 Watashi's BG(01dp)

01dp不过由于数组过于大,开不开,学了搜索过了,先记录下 还有一种方法 #include<stdio.h> #include<algorithm> using...

3657
来自专栏数据结构与算法

边双联通分量与割边

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双联通分量 双联通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 边双联通分量 对于一个...

3686
来自专栏用户2442861的专栏

Python-OpenCV 处理图像(二):滤镜和图像运算

喜欢自拍的人肯定都知道滤镜了,下面代码尝试使用一些简单的滤镜,包括图片的平滑处理、灰度化、二值化等:

1071

扫码关注云+社区