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

小鱼儿 2022-05-14 03:35 279阅读 0赞

*  # 最短路径-Dijkstra(迪杰斯特拉)算法 #

--------------------

*  ## 网图的最短路： ##

最短路径，是指两顶点之间经过的边上权值之和最小的路径，并且我们称路径的第一个顶点是源点，最后一个顶点是终点

*  ## Dijkstra(迪杰斯特拉)算法： ##

### 概况： ###

按路径长度递增的次序产生的最短路径算法，通过一步步计算出路径之间顶点的最短路径，在此过程中都是基于已经求出的最短路径基础上，求得更远顶点的最短路径

### 思想： ###

设**当前已经求得的最短路径边集为\{MT\}**，**当前最短路终点与相连点（不在MT中）的距离（与起点距离）集合为\{WP\}**

每次都在WP中取与当前终点最近的一个点，将最短边L加入最短路径集\{MT\}，记此时新的终点为NewEnd

扫描不在最短路径中的所有点，如果 **NewEnd+L<Dis**(*表示起点到当前扫描点的距离*)，更新最短路

### 相似算法： ###

在最小生成树上用过类似思想，只不过最小生成树要求全部点都要连通

**留个传送门：**[最小生成树-Prim(普里姆)算法][-Prim]

### 图解： ###

**两个工具：**

**a.Path\[MAX\_SIZE\]：记录路径，Path\[i\]是i的前驱，路径方向 Path\[i\] -> i**

**b.Short\_Path\[MAX\_SIZE\]：Short\_Path\[i\] 表示 从起点Start（不一定是0或者1）到 i 的最短路径大小**

以下图为栗，v0为起点

![70][]

首先记录下v0到相连点的距离（明显是v1和v2），进行初始化，此时：

**Path：**\{ 0 0 0 0 0 0 0 0 0 \} --- 初始化0

**Short\_Path：**\{ 0 1 5 65535 65535 65535 65535 65535 65535 \} --- v0与v1距离为1，v0与v2距离为5

选出最短Short\_Path 中的最短距，v1成为新的最短路终点，如下图，此时v1与v2，v3，v4相连

所有v0-v3=1+7=8 .......，可得（扫描更新后）：

**Path：**\{ 0 0 1 1 1 0 0 0 0 \}

**Short\_Path：**\{ 0 1 4 8 6 65535 65535 65535 65535 \}

![70 1][]

一样，选出Short\_Path中此时没有加入最短路顶点的最短路（红色），也就是4，得到 v0-v1-v2 ，v2为最短路新顶点

![70 2][]

继续更新最短路，加入v4，v5，很明显，v0-v1-v4=6，而v0-v2-v4=5，路径更新为后者

**Path：**\{ 0 0 1 1 2 2 0 0 0 \}

**Short\_Path：**\{ 0 1 4 8 5 11 65535 65535 65535 \}

此时没有加入最短路的最小路径为5，也就是v4作为新终点

![70 3][]

按之前步骤继续往下走，直到v8：

**Path：**\{ 0 0 1 4 2 4 3 6 7 \}

**Short\_Path：**\{ 0 1 4 7 5 8 10 12 16 \}

如下图，**得到最短路径：*v0-v1-v2-v4-v3-v6-v7-v8*，最短路长度为16**

![70][]

### Short\_Path的利用： ###

Short\_Path 显然是每一次最短路径的延申，所以求得Start-End的最短路，同理，***Start到任意点的最短路都可以在Short\_Path 中查得***

### **算法复杂度：** ###

**O（n^2）**

*  ## Dijkstra模板： ##

#include <iostream>
    #include<memory.h>
    using namespace std;
    #define MAX_SIZE 1024
    #define INF 65535
    
    //邻接图
    struct MGrapth
    {
        int Vexs[MAX_SIZE];  //顶点表
        int Arc[MAX_SIZE][MAX_SIZE];  //邻接矩阵
        int Num_Vertext,Num_Edges;  //顶点数，边数
    };
    MGrapth Map;
    
    int Path[MAX_SIZE];   /*表示路径 Path[i]->i*/
    int Short_Path[MAX_SIZE]; /*Start->i 的最短路径和*/
    bool Vis[MAX_SIZE];   /*当前最短路径结点true*/
    int Res;  /*最短路*/
    
    void Init(int n,int m)
    {
        Res=0;
        memset(Vis,0,sizeof(Vis));
        memset(Path,0,sizeof(Path));
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                Map.Arc[i][j]=INF;
        Map.Num_Vertext=n;
        Map.Num_Edges=m;
    }
    
    void Dijkstra(int Start)
    {
        int v,w,k,Min;
        for(v=0;v<Map.Num_Vertext;v++)
            Short_Path[v]=Map.Arc[Start][v];  /*Start到相连结点的距离*/
    
        Short_Path[Start]=0;   /*Start->Start 的距离为0*/
        Vis[Start]=1;   /*Start为当前最短路径结点*/
    
        for(v=1;v<Map.Num_Vertext;v++)
        {
            Min=INF;
            for(w=0;w<Map.Num_Vertext;w++)
            {
                if(!Vis[w]&&Short_Path[w]<Min)
                {
                    k=w;
                    Min=Short_Path[w];
                }
            }
            Vis[k]=true; /*找出最短路到散点的最小值，将该散点连入最短路*/
    
            for(w=0;w<Map.Num_Vertext;w++)  /*更新最短路*/
            {
                if(!Vis[w]&&Min+Map.Arc[k][w]<Short_Path[w])  /*图中某点到v0的距离比当前路短，更新*/
                {
                    Short_Path[w]=Min+Map.Arc[k][w];
                    Path[w]=k;
                }
            }
        }
    }

[-Prim]: https://blog.csdn.net/SZU_Crayon/article/details/82182016
[70]: /images/20220514/c7e4ea3e1c45416fa85e938e017cda6d.png
[70 1]: /images/20220514/c28102f9058a471a800f91e62add99dd.png
[70 2]: /images/20220514/88354a0dfe2b4e49a5fc5fefcc62e95e.png
[70 3]: /images/20220514/de51e8232f824f26b12a2eb316c43726.png