算法:最短路径之迪杰斯特拉(Dijkstra)算法

对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法。本文先来讲第一种,从某个源点到其余各顶点的最短路径问题。

这是一个按路径长度递增的次序产生最短路径的算法,它的大致思路是这样的。

比如说要求图7-7-3中顶点v0到v1的最短路径,显然就是1。由于顶点v1还与v2,v3,v4连线,所以此时我们同时求得了v0->v1->v2 = 1+3 = 4, v0->v1->v3 = 1 +7 = 8, v0->v1->v4 = 1+5 = 6。

现在我们可以知道v0到v2的最短距离为4而不是v0->v2 直接连线的5,如图7-7-4所示。由于顶点v2还与v4,v5连线,所以同时我们求得了v0->v2->v4其实就是v0->v1->v2->v4 = 4+1=5,v0->v2->v5 = 4+7 = 11,这里v0->v2我们用的是刚才计算出来的较小的4。此时我们也发现v0->v1->v2->v4 = 5要比v0->v1->v4 = 6还要小,所以v0到v4的最短距离目前是5,如图7-7-5所示。

当我们要求v0到v3的最短路径时,通向v3的三条边,除了v6没有研究过外,v0->v1->v3 = 8, 而v0->v4->v3 = 5 +2 = 7,因此v0到v3的最短路径为7,如图7-7-6所示。

如上所示,这个算法并不是一下子就求出来v0到v8的最短路径,而是一步步求出它们之间顶点的最短距离,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到想要的结果。

程序代码如下:(改编自《大话数据结构》)

#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];
typedef int ShortPathTable[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];
        }
    }

}
/*  Dijkstra算法,求有向网G的pos顶点到其余顶点v的最短路径P[v]及带权长度D[v] */
/*  P[v]的值为前驱顶点下标,D[v]表示pos到v的最短路径长度和 */
/*  pos 取值 0~MG.numVertexs-1 */
void ShortestPath_Dijkstra(MGraph MG, int pos, PathArc P, ShortPathTable D)
{
    int v, w, k, min;
    int final[MAXVEX];/* final[w]=1表示求得顶点pos至w的最短路径 */
    for (v = 0; v < MG.numVertexes; v++)
    {
        final[v] = 0;/* 全部顶点初始化为未知最短路径状态 */
        D[v] = MG.arc[pos][v];/* 将与pos点有连线的顶点加上权值 */
        P[v] = 0;/* 初始化路径数组P为0  */
    }

    D[pos] = 0; /*说明源点pos没有到自身的路径 */
    P[pos] = -1; /* -1表示自身无前驱顶点*/
    final[pos] = 1;/* pos至pos不需要求路径 */
    /* 开始主循环,每次求得pos到某个v顶点的最短路径 */
    for (v = 1; v < MG.numVertexes; v++)
    {
        min = INFINITY;/* 当前所知离pos顶点的最近距离 */
        for (w = 0; w < MG.numVertexes; w++)/* 寻找离pos最近的顶点 */
        {
            if (!final[w] && D[w] < min)
            {
                k = w;
                min = D[w];/* w顶点离pos顶点更近 */
            }
        }
        final[k] = 1;/* 将目前找到的最近的顶点置为1 */
        for (w = 0; w < MG.numVertexes; w++)/* 修正当前最短路径及距离 */
        {
            if (!final[w] && (min + MG.arc[k][w] < D[w]))
            {
                /*  说明找到了更短的路径,修改D[w]和P[w] */
                D[w] = min + MG.arc[k][w];/* 修改当前路径长度 */
                P[w] = k;
            }
        }
    }
    /* 结束循环,若P[w] = 0;说明顶点w的前驱为pos */
}


int main(void)
{
    MGraph MG;
    PathArc P;
    ShortPathTable D;
    int i, j, pos = 2;
    CreateMGraph(&MG);
    ShortestPath_Dijkstra(MG, pos, P, D);

    cout << "逆序最短路径如下:" << endl;
    for (i = 8; i >= 0; i--)
    {
        j = i;
        while (P[j] != -1 && P[j] != 0)
        {
            cout << "v" << j << "<-" << "v" << P[j] << "  ";
            j = P[j];
        }
        cout << "v" << j << "<-" << "v" << pos << "  ";
        cout << endl;

    }
    cout << endl;

    return 0;
}

输出为:

其中CreateMGraph函数创建出来的邻接矩阵如图7-7-7所示。

相信经过上面的分析,大家可以自己进行循环跑程序分析了,循环结束后final = { 1, 1, 1, 1, 1, 1, 1, 1, 1 }表示所有顶点均完成了最短路径的查找工作。此时D = { 4, 3, 0, 3, 1, 4, 6, 8, 12 }, 注意我们在前面说过Dijkstra算法可以求某个源点到其他顶点的最短路径,现在我们上面程序中给出的pos = 2, 即源点为v2, 所以D[2] = 0 表示没有到自身的路径。D数组表示v2到各个顶点的最短路径长度,比如D[8] =1+2 + 3 + 2 + 4 = 12。此时P = { 1, 0, -1, 4, 0, 4, 3, 6, 7 }, 可以这样来理解,P[2] = -1 表示v2没有前驱顶点,P[1] = P[4] = 0 表示v1和v4的前驱顶点为源点v2。再比如P[8] = 7,表示v8的前驱是v7;再由P[7] = 6,表示v7的前驱是v6; P[6] = 3 表示v6的前驱是v3, 这样就可以得到v2 到 v8的最短路径为v2->v4->v3->v6->v7->v8,从上面的程序输出也可以验证我们的推测。

其实最终返回的数组D和数组P,是可以得到v2到任意一个顶点的最短路径和路径长度的,也就是说我们通过Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以得到此算法的时间复杂度为O(n^2),如果我们要得到任一顶点到其余顶点的最短路径呢?最简单的办法就是对每个顶点都当作源点进行一次Dijkstra算法,等于在原有算法的基础上,再来一次循环,此时整个算法的时间复杂度就为O(n^3)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏诸葛青云的专栏

Python识别验证码!学会这步,百分之60的网站你基本都能识别了!

127是我们设定的阈值,像素值大于127被置成了0,小于127的被置成了255。处理后的图片变成了这样

1060
来自专栏PPV课数据科学社区

【学习】请速度收藏,Excel常用电子表格公式大全

1、查找重复内容公式:=IF(COUNTIF(A:A,A2)>1,”重复”,””)。 2、用出生年月来计算年龄公式:=TRUNC((DAYS360(H6,”2...

3598
来自专栏数据的力量

Excel公式大全,高手进阶必备

1505
来自专栏QQ音乐技术团队的专栏

GIF简述及其在QQ音乐的应用

GIF(Graphics Interchange Format)是CompuServe公司在1987年开发的图像文件格式,原义是图像互换格式。GIF是一种基于L...

7120
来自专栏PPV课数据科学社区

Excel公式大全,高手进阶必备!

第一部分:常用函数和公式 查找重复内容公式:=IF(COUNTIF(A:A,A2)>1,"重复","")。 用出生年月来计算年龄公式:=TRUNC((DAYS3...

3222
来自专栏章鱼的慢慢技术路

OpenGL基本框架与三维对象绘制

1542
来自专栏落影的专栏

Metal入门教程(二)三维变换

上一篇的教程介绍了如何绘制一张图片,这次的目标是把图片显示到3D物体上,并进行三维变换。

1906
来自专栏机器学习算法与Python学习

TensorFlow:TensorBoard可视化

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 我们会再接再厉 成为全网优质的技术类...

64812
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列十二:多尺度的图像细节提升。

无意中浏览一篇文章,中间提到了基于多尺度的图像的细节提升算法,尝试了一下,还是有一定的效果的,结合最近一直研究的SSE优化,把算法的步骤和优化过程分享给大家。...

2508
来自专栏小樱的经验随笔

一步一步深入理解Dijkstra算法

先简单介绍一下最短路径: 最短路径是啥?就是一个带边值的图中从某一个顶点到另外一个顶点的最短路径。 官方定义:对于内网图而言,最短路径是指两顶点之间经过的边...

3383

扫码关注云+社区

领取腾讯云代金券