Dijkstra求最短路算法 ( 超级超级详细的 ) 不断更新中

ゞ浴缸里的玫瑰 2021-07-24 23:28 378阅读 0赞

## Dijkstra求最短路 ##

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

##### 最短路问题 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center]  
先讲讲朴素版本的

##### Dijkstra算法 #####

> 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

我们先看看从1号点到n号点的最短距离怎么求。

##### 实现过程 #####

int g[N][N];  // 存储每条边
    int dist[N];  // 存储1号点到每个点的最短距离
    bool st[N];   // 存储每个点的最短路是否已经确定，若确定则st[i]=true;

S集合表示：当前已经确定最短距离的点。

##### 代码 #####

int Dijkstra()
    { 
        memset(dist,0x3f,sizeof dist);//除1号结点外，其他均初始为无穷大
        dist[1]=0;
        for(int i=0;i<n;i++) //n次迭代，每次寻找不在s中距离最近的点t
        { 
            int t=-1;// 便于更新第一个点
            for(int j=1;j<=n;j++)
              if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
            st[t]=true;  //将t加到s中
            for(int j=1;j<=n;j++)  //用t更新其他点的距离
              dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        if(dist[n]==0x3f3f3f3f) return -1; //路径不存在
        else return dist[n];
    }

是不是对这个代码和过程感到特别懵逼，来，我们上个图模拟一遍  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 2]  
如图1，图中有三个结点1，2，3，1到2结点距离为2，2到3结点距离为1，1到3结点距离为4。刚开始时，对每个点的`dist[]`进行初始化，`dist[1]=0`，`dist[2]=0x3f`，`dist[3]=0x3f`。 此时S集合为空，然后我们将距离起点最近的点加入S集合，显然1号结点距离起点的距离为0，是距离起点最近的，将其加入S集合。（重点强调起点指的是1号结点，S集合是当前已经确定最短距离点的集合）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 3]

然后我们用1号结点去更新其他点到起点的最近距离，1结点到2结点距离`g[1][2]=2`，小于`0x3f`，则`dist[2]=2`，1结点到3结点距离`g[1][3]=4`，小于`0x3f`，则`dist[3]=4`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 4]  
用1号结点将所有点的距离更新完毕后，此时S集合中有1号结点，接下来我们让距离我们刚加入的1号结点最近的点加入集合，显然为2号结点，2号结点进入S集合，此时S集合中有1,2号结点。然后用2号结点去更新3号结点到起点的距离。`dist[3]=4`大于 `dist[2]+1=3`,`dist[3]`被更新为3，最后将3号结点加入S集合。至此，所有点到起始结点的最短距离都已被找出。`dist[n]`即为n号节点到1号节点的最短距离。

接下来给出模板  
朴素版dijkstra算法  
时间复杂是 O(n^2+m), n 表示点数，m 表示边数

int g[N][N];  // 存储每条边
    int dist[N];  // 存储1号点到每个点的最短距离
    bool st[N];   // 存储每个点的最短路是否已经确定
    
    // 求1号点到n号点的最短路，如果不存在则返回-1
    int dijkstra()
    { 
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        for (int i = 0; i < n - 1; i ++ )
        { 
            int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
    
            // 用t更新其他点的距离
            for (int j = 1; j <= n; j ++ )
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    
            st[t] = true;
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

好了接下来我们来看一道模板题，实践是检验真理的唯一标准

[AcWing 849. Dijkstra求最短路 I][AcWing 849. Dijkstra_ I]

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。  
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。  
**输入格式**  
第一行包含整数n和m。  
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。  
**输出格式**  
输出一个整数，表示1号点到n号点的最短距离。  
如果路径不存在，则输出-1。  
**数据范围**  
1≤n≤500,  
1≤m≤105,  
图中涉及边长均不超过10000。  
**输入样例：**  
3 3  
1 2 2  
2 3 1  
1 3 4  
**输出样例：**  
3

题意很简单，在一个有向图中，求出1号结点到n号结点的最短距离，我们所举的第一个图示样例，就是这道题的数据。虽然是道模板题，但在具体实现过程中，会有很多小细节值得我们去留意和思考。

##### 完整代码 #####

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int N=510;
    int g[N][N];    //稠密图用邻接矩阵存储比较节省空间
    int dist[N];    //dist[i] i结点到起始点(1号结点)的距离
    bool st[N] ;    //st[i] 用于标记i结点的最短路是否确定，若确定st[i]=true;
    int n,m;
    int Dijkstra()   //套用模板
    { 
        memset(dist,0x3f,sizeof dist);//除1号结点外，其他均初始为无穷大
        dist[1]=0;
        for(int i=0;i<n;i++) //n次迭代，每次寻找不在s中距离最近的点t
        { 
            int t=-1;// 便于更新第一个点
            for(int j=1;j<=n;j++)
              if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
            st[t]=true;  //将t加到s中
            for(int j=1;j<=n;j++)  //用t更新其他点的距离
              dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        if(dist[n]==0x3f3f3f3f) return -1; //路径不存在
        else return dist[n];
    }
    int main()
    { 
        scanf("%d%d",&n,&m);
        memset(g,0x3f,sizeof g);   //邻接矩阵的初始化，由于求的是最小值，因此初始为无穷大
        while(m--)
        { 
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            g[x][y]=min(g[x][y],z); //重边中去取最小值
        }
        printf("%d\n",Dijkstra());
        return 0;
    }

如果有些地方不明白的话，不要着急，接着往下看

##### 常见问题合集 #####

1.  0x3f为什么赋值的时候可以`memset(dist,0x3f,sizeof dist)`但是到后面验证的时候必须是`if(dist[n]==0x3f3f3f3f)`而不能是`if(dist[n]==0x3f)`  
    **回答:**：`memset`是按字节来初始化的，int包含4个字节，所以初始化之后的值就是`0x3f3f3f3f`。
2.  为什么要用`memset(dist,0x3f,sizeof dist)`来初始化  
    **回答:**：0x3f3f3f3f的十进制是1061109567，是1e9级别的（和0x7fffffff一个数量级，0x7fffffff代表了32-bit int的最大值），而一般场合下的数据都是小于1e9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上`0x3f3f3f3f+0x3f3f3f3f=2122219134`，这非常大但却没有超过32-bit int的表示范围，所以`0x3f3f3f3f`还满足了我们“无穷大加无穷大还是无穷大”的需求。
3.  `for(int i=0;i<n;i++) { t=-1 }` 这里为什么`t`要赋值为 `-1`  
    **回答:** 由于每一次都要找到还没有确定最短路距离的所有点中，距离当前的点最短的点。`t = - 1`是为了在`st`这个集合中找第一个点更新时候的方便所设定的。
4.  如果是问编号a到b的最短距离该怎么改呢? （好问题）  
    **回答：** 初始化时将 `dist[a]=0`,以及返回时`return dist[b]`。
5.  自环和重边对 Dijkstrea算法有影响吗？  
    **回答：** 自环在朴素版dijkstra算法中是没有任何影响的，所以自环的权值是多少都可以，只要不是负数就行。而重边时，我们去取重边中的最小值 即代码`g[x][y]=min(g[x][y],z)`。
6.  为什么要用邻接矩阵去存贮，而不是邻接表？  
    **回答：** 我们采用邻接矩阵还是采用邻接表来表示图，需要判断一个图是稀疏图还是稠密图。稠密图指的是边的条数|E|接近于|V|²，稀疏图是指边的条数|E|远小于于|V|²（数量级差很多）。本题是稠密图，显然稠密图用邻接矩阵存储比较节省空间，反之用邻接表存储。

接下来讲讲堆优化版的Dijkstra算法

##### 优化版Dijkstra #####

##### 实现过程 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 5]  
堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。

1.  一号点的距离初始化为零，其他点初始化成无穷大。
2.  将一号点放入堆中。
3.  不断循环，直到堆空。每一次循环中执行的操作为：  
    弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。  
    用该点更新临界点的距离，若更新成功就加入到堆中。

为了实现这个过程，我们首先要定义几个数组和函数。

int dist[N];         // 存储所有点到1号点的距离
    bool st[N];     // 存储每个点的最短距离是否已确定

建立邻接表的函数（这里就不展开详讲了）

cost int N=1e5+10;  //N为边的数量
    int h[N];   // h[i]存储编号为i结点的单链表的头结点的下标(地址)
    int e[N];   // e[i]存储下标为i结点的编号
    int ne[N];  // ne[i]存储下标为i结点所指向的下一个结点的下标(地址)
    int idx;    // idx 存储当前已经用到了哪个点
    int w[N]
    void add(int x,int y,int z) //编号为a和b的结点之间建立一条边,即a所对应的单链表中在头结点后插入b
    { 
        e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
    }

定义一个优先队列来维护距离最近的点。

priority_queue<PII,vector<PII>,greater<PII>>heap 
     // first存储距离，second存储节点编号

接下来给出模板  
时间复杂度 O(mlogn), n 表示点数，m 表示边数

typedef pair<int, int> PII;
    
    int n;      // 点的数量
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储所有点到1号点的距离
    bool st[N];     // 存储每个点的最短距离是否已确定
    
    // 求1号点到n号点的最短距离，如果不存在，则返回-1
    int dijkstra()
    { 
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({ 0, 1});      // first存储距离，second存储节点编号
    
        while (heap.size())
        { 
            auto t = heap.top();
            heap.pop();
    
            int ver = t.second, distance = t.first;
    
            if (st[ver]) continue;
            st[ver] = true;
    
            for (int i = h[ver]; i != -1; i = ne[i])
            { 
                int j = e[i];
                if (dist[j] > distance + w[i])
                { 
                    dist[j] = distance + w[i];
                    heap.push({ dist[j], j});
                }
            }
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

看看这道模板题  
[AcWing 850. Dijkstra求最短路 II][AcWing 850. Dijkstra_ II]  
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。  
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。  
**输入格式**  
第一行包含整数n和m。  
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。  
**输出格式**  
输出一个整数，表示1号点到n号点的最短距离。  
如果路径不存在，则输出-1。  
**数据范围**  
1≤n,m≤1.5×105,  
图中涉及边长均不小于0，且不超过10000。  
**输入样例：**  
3 3  
1 2 2  
2 3 1  
1 3 4  
**输出样例：**  
3

这道题的数据范围相比上道题加强了很多，可以看出是个稀疏图，如果再用朴素版的Dijkstra算法,很容易超时，因此我们用优化版Dijkstra来实现。

##### 完整代码 #####

/* 朴素版 Dijkstras算法适合于稠密图，时间复杂度为O(n^2) 优化版 Dijkstras算法适合于稀疏图，时间复杂度为O(m*logn) */
    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<vector>
    #include<cstring>
    using namespace std;
    typedef pair<int,int> PII;
    const int N=1e6+10;
    int e[N],ne[N],h[N],w[N],idx;
    int dist[N];
    int st[N];
    int n,m;
    void add(int x,int y,int z)
    { 
        e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
    }
    int Dijkstra()
    { 
        memset(dist,0x3f,sizeof dist);
        dist[1]=0;
        priority_queue<PII,vector<PII>,greater<PII>>heap;
        heap.push({ 0,1});
        while(heap.size())
        { 
            PII t=heap.top();  //取出不在s中距离最短的点
            heap.pop();  
            int ver=t.second,distance=t.first;
            if(st[ver])  continue;  //如果该点已经确定了最短距则跳过
            st[ver]=true;           //否则将该点加入s中
            for(int i=h[ver];i!=-1;i=ne[i])  //用该点确定其他点的最短距离
            { 
                int j=e[i];
                if(dist[j]>distance+w[i])
                { 
                    dist[j]=distance+w[i];   //更新距离
                    heap.push({ dist[j],j});
                }
            }
        }
        if(dist[n]==0x3f3f3f3f) return -1;
        else return dist[n];
    }
    int main()
    { 
        cin>>n>>m;
        memset(h,-1,sizeof h);
        while(m--)
        { 
            int x,y,z;
            cin>>x>>y>>z;
            add(x,y,z);
        }
        cout<<Dijkstra()<<endl;
        return 0;
    }

问题会持续更新，欢迎评论区留言。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210724/61381ceee2d34c4cafd1ea313bbe15b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210724/95a15bb79a5f453d87da3b2e3a1a9eee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210724/e9325d919f7f463581b4a18955374953.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210724/d2104de92cbf44448a39fec247f9b855.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210724/1b65a806d9694b0b89fb10c6ec7d294b.png
[AcWing 849. Dijkstra_ I]: https://www.acwing.com/problem/content/description/851/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210724/cc113f9fbc0e4ca281f1e484f50900e8.png
[AcWing 850. Dijkstra_ II]: https://www.acwing.com/problem/content/852/