最短路径 | 深入浅出Dijkstra算法（一）

参考网址： https://www.jianshu.com/p/8b3cdca55dc0

写在前面：

上次我们介绍了神奇的只有五行的 Floyd-Warshall 最短路算法，它可以方便的求得任意两点的最短路径，这称为“多源最短路”。

这次来介绍指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。

Dijkstra算法

与 Floyd-Warshall 算法一样，这里仍然使用二维数组 e 来存储顶点之间边的关系，初始值如下。

我们还需要用一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程，我们可以称 dis 数组为“距离表”，如下。

初始状态

我们将此时 dis 数组中的值称为最短路的“估计值”。

既然是求 1 号顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。

通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”，即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。

为什么呢？你想啊，目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。因此 1 号顶点到其它顶点的路程肯定没有 1 号到 2 号顶点短，对吧 O(∩_∩)O~

既然选了 2 号顶点，接下来再来看 2 号顶点有哪些出边呢。有 2->3 和 2->4 这两条边。

先讨论通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。也就是说现在来比较 dis[3]和 dis[2]+e[2][3]的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程，dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，e[2][3]表示 2->3 这条边。所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->3 这条边，到达 3 号顶点的路程。

我们发现 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新为 10。这个过程有个专业术语叫做“松弛”。即 1 号顶点到 3 号顶点的路程即 dis[3]，通过 2->3 这条边松弛成功。 这便是 Dijkstra 算法的主要思想：通过 “边” 来松弛 1 号顶点到其余各个顶点的路程。

同理通过 2->4（e[2][4]），可以将 dis[4]的值从 ∞ 松弛为 4（dis[4]初始为 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新为 4）。

刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为：

第一轮边松弛

接下来，继续在剩下的 3、4、5 和 6 号顶点中，选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组，当前离 1 号顶点最近是 4 号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边（4->3，4->5 和 4->6）用刚才的方法进行松弛。松弛完毕之后 dis 数组为：

第二轮边松弛

继续在剩下的 3、5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 3 号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边（3->5）进行松弛。松弛完毕之后 dis 数组为：

第三轮边松弛

继续在剩下的 5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 5 号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后 dis 数组为：

第四轮边松弛

最后对 6 号顶点的所有出边进行松弛。因为这个例子中 6 号顶点没有出边，因此不用处理。到此，dis 数组中所有的值都已经从“估计值”变为了“确定值”。

最终 dis 数组如下，这便是 1 号顶点到其余各个顶点的最短路径。

第五轮边松弛

OK，现在来总结一下刚才的算法。Dijkstra算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

基本步骤如下：

① 将所有的顶点分为两部分：已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始，已知最短路径的顶点集合 P 中只有源点一个顶点。我们这里用一个 book[i] 数组来记录哪些点在集合 P 中。例如对于某个顶点 i，如果 book[i] 为 1 则表示这个顶点在集合 P 中，如果 book[i] 为 0 则表示这个顶点在集合 Q 中。【初始化book标记】

② 设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把 dis[i] 设为 e[s] [i] 。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞ 。【初始化dis距离表】

③ 在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u（即 dis[u] 最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。例如存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是 dis[u]+e[u] [v]。如果这个值比目前已知的 dis[v] 的值要小，我们可以用新值来替代当前 dis[v] 中的值。【取dis最小(访问过的除外)，边松弛】【核心】

④ 重复第 ③ 步，如果集合 Q 为空，算法结束。最终 dis 数组中的值就是源点到所有顶点的最短路径。

关于Dijkstra的两个问题：

在博客中看到两个比较有趣的问题，也是在学习Dijkstra时，可能会有疑问的问题。

问题一：边权≠边长

当我们看到上面这个图的时候，凭借多年对平面几何的学习，会发现在“三角形ABC”中，满足不了构成三角形的条件(任意两边之和大于第三边)。纳尼，那为什么图中能那样子画？

还是“三角形ABC”，以A为起点，B为终点，如果按照平面几何的知识，“两点之间线段最短”，那么，A到B的最短距离就应该是6(线段AB)，但是，实际上A到B的最短距离却是3+2=5。这又怎么解释？

其实，之所以会有上面的疑问，是因为对边的权值和边的长度这两个概念的混淆， $边的权值≠边的长度$ 。之所以这样画，也只是为了方便理解（每个人写草稿的方式不同，你完全可以用别的方式表示，只要便于你理解即可）。

问题二：可以完美地扫到图中每个点
按照Dijkstra算法，是可以完美地扫到图中地每一个点地，倘若你不确定这一点，可以自己再手动模拟一下该算法的过程，相信你会收获颇丰。

代码实现：

通过邻接矩阵的Dijkstra时间复杂度是 $O(N^2)$ 。
对于边数 $M$ 少于 $N^2$ 的稀疏图来说（我们把 $M 远小于N^2$ 的图称为稀疏图，而 $M$ 相对较大的图称为稠密图），我们可以用邻接表来代替邻接矩阵，使得整个时间复杂度优化到 $O((M+N)logN)$ 。
请注意！在最坏的情况下 $M$ 就是 $N^2$ ，这样的话 $MlogN$ 要比 $N^2$ 还要大。但是大多数情况下并不会有那么多边，因此 $(M+N)logN$ 要比 $N^2$ 小很多。

【邻接矩阵实现Dijkstra】

// Dijkstra邻接矩阵 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int INF=0x3f3f3f3f;// 正无穷 
const int Maxsize=1e3+5;// 顶点数 
int e[Maxsize][Maxsize];// 邻接矩阵 
int book[Maxsize];// 标记 
int dis[Maxsize];// 距离表 
int n,m;// n:节点；m:边 
int v1,v2,w;

int main()
{
    scanf("%d%d",&n,&m);
    // 初始化邻接矩阵 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)e[i][j]=0;
            else e[i][j]=INF;
        }
    }
    // input vex，arc 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v1,&v2,&w);
        e[v1][v2]=w;
    }
    // init dis
    for(int i=1;i<=n;i++)
    {
        dis[i]=e[1][i];
    }
    // init book
    for(int i=1;i<=n;i++)book[i]=0;
    book[1]=1;// 程序以源点为 1来举例 
    
    for(int i=1;i<=n-1;i++)// n-1次循环，而非n次循环(因为 1节点自身已确定) 
    {
        // 找到距离1号顶点最近的顶点(min_index) 
        int min_num=INF;
        int min_index=0;
        for(int k=1;k<=n;k++)// n次循环 
        {
            if(min_num>dis[k] && book[k]==0)
            {
                min_num=dis[k];
                min_index=k;
            }
        }
        book[min_index]=1;// 标记 
        for(int j=1;j<=n;j++)
        {
            // 节点 min__index =》j 有边 
            if(e[min_index][j]<INF)
            {
                // 加入之后使得距离变得更短
                // 可以写为 dis[j]=min(dis[j],dis[min_index]+e[min_index][j]); 
                if(dis[j]>dis[min_index]+e[min_index][j])
                {
                    dis[j]=dis[min_index]+e[min_index][j];
                }
            }
        }
    }
    // print
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    puts("");// 换行 
    return 0;
}

【(数组)邻接表实现Dijkstra】

PS：数组实现邻接表可能较难理解，可以看一下这里

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int VMaxsize=1e3+5;// 顶点数 
const int AMaxsize=1e6;// 边数 
int n,m;// n:顶点数；m:边数 
int v1[AMaxsize],v2[AMaxsize],w[AMaxsize];
int first[VMaxsize];
int next[VMaxsize];

int main()
{
    scanf("%d%d",&n,&m);
    // init first
    for(int i=1;i<=n;i++)first[i]=-1;
    //【core code】 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v1[i],&v2[i],&w[i]);
        next[i]=first[v1[i]];
        first[v1[i]]=i;
    }
    // 遍历 
    for(int i=1;i<=n;i++)
    {
        int temp=first[i];
        while(temp!=-1)
        {
            printf("%d->%d : %d
",v1[i],v2[i],w[i]);
            temp=next[temp];
        }
    }
    return 0;
}

Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。

根据这个原理，用Dijkstra算法求最短路径的图不能有负权边，因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。

那么，有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法（即“单源最短路径”问题）呢？答案是有的，Bellman-Ford算法就是一种。（我们已经知道了Floyd-Warshall可以解决“多源最短路”问题，也要求图的边权均为正）

通过邻接矩阵的Dijkstra时间复杂度是 $O(N^2)$ 。其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用优先队列（堆）来优化，使得这一部分的时间复杂度降低到 $O(logN)$ 。这个我们将在后面讨论。

作者：0与1的邂逅
链接：https://www.jianshu.com/p/8b3cdca55dc0
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。