第十六章 Dijkstra算法的讲解以及证明（与众不同的通俗证明）

一、Dijkstra的用途

Dijkstra算法是用来解决边权不是一，并且是单源最短路问题的。好的，大概率这句话没有看懂。没关系的，接下来将通俗地说明一下。

边权是指边的长度，也就两个点之间的距离。单源指的是从同一个起点出发，前往不同的点。

例如下图所示：

那么从起点到某个点的最短路径问题，就是我们的dijkstra算法需要解决的问题。

二、dijkstra算法思路

（以下将采用逆向思维的方式进行叙述，即将起点看作终点，起点到终点和从终点到起点的最短路一定是一致的。）

1、最短路的性质

最短路，顾名思义就是这条路线是所有能从该点带到终点的路线中，最短的。那么我们可以用下面的图示和数学表达式描述该性质：

（该图中只是描述一下一些关键点，不是具体的路线，中间具体的中转点忽视了，所以这里用的虚线，仅仅表示一段路的起点和终点。）

如果我们不从U到V，那么我们必须先到达另外一个点A（这个A点指的是任意一个能到V的，除了U之外的点），再到V。

由于我们的黑色路径是最短路，那么必定满足下面的关系式：

d[u] ：从U到V的最短路径
d[A]：从A到V的路径
W：从U到A的路径

只要我们的d[U]是最短的，那么上面这个式子永远成立！

我们可以证明一下：

假设d[U]是从U到V最短的路径，同时存在另外一个点A，使得该定理不成立：

即d[U]>d[A]+W。那么该式子说明，从U到A再到V的路径小于d[U]，但是我们的前提是d[U]是最小值，不可能比这个还小，因此，这个假设不成立。即上述的定理是正确的。

如果一段路径不满足上述的定理，那么这段路就不是最短的，也就是说存在一个点使得：d[U]>d[A]+W。我们发现这个式子的右端是一个新的路径，左端是原来的路径，我们的原来路径竟然比新的路径长，这个事实除了说明当前路径不是最短路之外，还能够用来更新我们的d[U]。我们就可以让：d[U]=d[A]+W。这个过程称之为松弛操作，其实我们可以想象成一根橡皮筋。原来的长度是d[U],绷得很紧，长度很长，但是我们换个路径，松弛一下橡皮筋。那么这个橡皮筋就没有那么紧绷了，长度也适当缩小了。

2、算法思路：

基于上面的定理，我们只要找到某条路径恒满足上面的定理，则该路径就是最短路。

以下面的例子为例：

一开始我们不知道最短路径，所及假设所有点到终点的路是无穷大。而两个未连接的点之间距离也初始化为无穷大。

当前我们所了解的最短路径一定是，终点自身到自身，这个距离是0，这一定是最短路，毋庸置疑，因为边都是正的。

从我们的公式：d[U]<=d[A]+w来看，

如果不是最短路，那么一定存在：d[U] > d[A] + w 。边w都是固定死的，所以我们所用的d[A]越小，这个式子越容易成立。因此我们利用d[终点]=0去松弛所有点。

松弛过后的结果，我们发现只有此时的终点的邻接点得到了有效的更新，即图中的蓝线所覆盖的点，其余依然是无穷（因为：0+无穷=无穷）。

我们这里暂时把这个用来松弛所有点的点，称之为中间点。
因此，我们这样松弛一遍后，改变的点一定是中间点的邻接点，那么我们为什么要这样做？

我们以第一次松弛为例子：
远处的点想要到达终点，必会经过终点的邻接点（即蓝色线覆盖的部分），**所以我们前面找到的最短路可能是远处点的最短路径中的一部分。**所以我们先找找近处的点的最短路，这样可以在找远处点的时候利用一下这些近处的最短路。

蓝色线枚举出了终点的邻接点，此时，我可以很负责的说，A点的最短路已经确定了。

为什么？

那么根据我们刚才的式子：

d[A]是指除了u之外，其余能到终点的点。

无论怎么走，它想到终点必须经过上图中的蓝色线所覆盖的点的其中之一，这是毋庸置疑的。
为什么？因为想到达终点必过它的邻接点，而我们的蓝色线枚举出了所有的A的邻接点。

(这里用dd[]表示上图中从某点到终点的距离)

那么公式中的d[U]就是图中的dd[A]，而公式中的d[A]，就是图中的，dd[C]或者dd[D]。
由于dd[A]已经小于了dd[C]和dd[D]。又因为边都是正的，也就是w>0。因此，我们的dd[a]必定恒小于
dd[C]+w，dd[D]+w。因此，这条等式恒成立，所以松弛过后，最短的那条路就是从A到终点的最短路。

可能会有人问，那我不走C和D，我可以走别的点呀，你怎么就知道A先到别的点再到终点是不行的呢？

好，我们假设存在这样的一个假象的路径，满足你的疑问，由于我们在枚举出了和A相连的所有点，即
A，C，D。所以你所假想的路径必定是经过这三个点之一的。

那么你假象的路径必定是这样的：A—>k---->（C或A或D）---->终点。即：dd1+dd2+(dd[C]或dd[A]或dd[D])。我从你这三种可能的路径中选一个最短的：即过A，不过C，D。那么你假象的最短路就是：

dd1+dd2+dd[A]。很明显，这条路径的长度大于我们刚才所得出的最短路：dd[A]。

因此，我们的结论成立，dd[A]就是A点到终点的最短路。

那么，你怎么就知道，D和C有可能没到最短路呢？（以点C为例子）
我们不凭空想象，我们依旧来假设验证一下。我们假设存在一个点S，使得当前的：dd[C]>dd[S]+W(S,C)。其中dd[S]=dd[A]+W[S,A]，因为我们的S无法直接到终点，所以我们可以让该点借助一下A点。

那么我们就看此时:dd[C]>dd[A]+W(S,C)+W(S,A)。这个有没有可能成立。答案是有可能的，因为我们的dd[C]>dd[A]。所以当我们的W(S,C)+W(S,A)小于dd[C]-dd[A]的时候，这个等式就成立了。因此是有可能存在这个样的一个点S的。

所以我们并不能保证此时的C和D是最短路径。

那么我们的得到怎样的启示呢？

我们只能保证每次松弛过后的路径中的最小的那个，是最短路。

---

接着，根据我们刚才的思路：要想剩余的点距离得到减小，必定要让他们完成松弛操作，而松弛操作的前提是：

d[U]>d[A]+W。所以我们的d[A]越小，越容易实现松弛，因此我们用刚刚得到的最短路：dd[A]去实现，即让dd[A]去松弛其余的未确定最短路的点。

松弛过后，我们发现，能够得到有效更新的点，也必定是A点的邻接点。即图中的绿色线所示：

由于其他点不过A，A的邻接点借助A到终点的路径长度已经被我们算出来了，而A的最短路已经确定了。那么A点就没用了。我们可以舍去A点，画出下面的等效图。

此时，我们就可以利用相同的套路了。根据我们刚才的定理：

我们只能保证每次松弛过后的路径中的最小的那个，是最短路。

因此，D到终点的最短路就确定了。

接着我们再利用D去松弛所有未确定的点。周而复始n次。因为松弛一次，能够确定一个点的最短路，所以共需要松弛n次。

这就是dijkstra的思路：

利用最短路的起点去松弛所有点，然后取出最小值，再利用该最小值所在路径的起点去松弛剩余点…

3、算法思想：

我们发现我们松弛的时候，是利用当前已知的最短路去松弛的所有点。这是一种贪心思想。即，我每次做出对当下而言最好的选择，每次都做对当下最好的，那么就有一定的可能从局部最优推出整体最优。

三、Dijkstra的实现

1、问题：

2、代码模板：

#include
#include
using namespace std;
const int N=510;
int g[N][N],dis[N];
bool s[N];
int n,m,a,b,c;
int dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=1;i<=n;i++)
    { 
        int t=-1;
        
        for(int j=1;j<=n;j++)
        {
            if(!s[j]&&(t==-1||dis[j]<dis[t]))t=j;
        }
        s[t]=true;
        
        for(int j=1;j<=n;j++)
        {
            dis[j]=min(dis[j],g[t][j]+dis[t]);
        }
    }
    if(dis[n]==0x3f3f3f3f)return -1;
    else return dis[n];
}
int main()
{
    memset(g,0x3f,sizeof g);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    cout<<dijkstra();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

3、代码分析：

4、问题解决：

（1）为什么用邻接矩阵

邻接矩阵是一个二维数组，他记录了所有可能存在的边，当边数较少的时候，它会存储很多没用的点。但是现在我们发现边的数量是10的5次方。所以基本上每两个点之间都有边，所以用邻接矩阵几乎不会浪费空间。

四、复杂度分析：

外循环n次，内循环2*n次，所以时间复杂度是O(N²)