学完了图论基础(一)和图论基础(二)之后，我们学会了如何储存一个图、遍历一个图。而这篇文章，将带大家领略图论最精彩的地方——单源最短路。
单源最短路，就是指在一个图中，对于一个点，求出这个点到剩下所有点的最短距离。就像算学校到北京各个角落的最短距离一样。目前，有两种算法可以解决这个问题：Dijkstra和Bellman-Ford。而今天这篇文章，将给大家带来Dijkstra单源最短路算法的详解。
在介绍Dijkstra算法之前，先稍微介绍一下它的发明者：
Edsger Wybe Dijkstra(1930.5.11~2002.8.6)
荷兰计算机科学家。
生于科学家庭，毕业于荷兰Leiden大学。
提出“goto有害论”，设计开发THE操作系统，提出信号量和PV原语，发明银行家算法，发明Dijkstra单源最短路算法。
获得1972有“计算机学诺贝尔奖”之称的图灵奖。
既然这样的图灵奖大佬，都用自己的姓氏“Dijkstra”来命名这样一个算法，足以可见这个算法的在的重要性和它的伟大之处。但是这个伟大的算法也不失它有趣而且易懂的一面。下面，就给大家详细解释Dijkstra算法是如何运作的。
首先，我们先明确一下目标。我们的目标是对于一个图，找到这个图一个点到所有点的距离。拿这个可爱的无向图举例：
我们的目标就是求1号点到所有点的距离。那么，这个怎么实现呢？
有一种很容易想到的方法就是把所有方法都走一遍，然后选出一种距离最短的走法，作为答案。这样的答案固然正确，但是这种做法在信息竞赛中叫做“暴力”，意思是它虽然很容易想到，但是运行的太慢了。有没有一种方式，能更迅速地找到最短的距离？
考虑一种情况。假设你现在在你家(1号点)，你只知道你家到学校(2号点)的最短距离为5和到公园(3号点)的最短距离为8。你现在想知道你家到咖啡厅(4号点)的最短距离，但是，你家并没有直接到咖啡厅的路。现在，想到咖啡厅就有两种选择，第一种是先到学校再去咖啡厅；另一种是先到公园再去咖啡厅，哪一种更快？
答案显然是第一种，第二种我们根本不用计算就知道不可行。因为第一种到学校的5加上到咖啡厅的1之后，发现这个距离是6。这个距离比到公园的都要短，说明就算公园到咖啡厅特别短，甚至挨着咖啡厅，我们都不可能会走公园这条路。这样就省的计算公园这条路了。这种“省的计算”，就是一种优化。
而这样可以推断，任何一个和学校相连的地方，如果它到学校的距离+5小于8，我们就根本不用考虑从公园走的路线。这样，优化的计算量就会大很多了。
那么这样的“减少计算量”的策略，如何应用于算法中呢？当我们确定到一个点u的最短距离为k时，我们枚举所有以这个点为起点的边。对于每一条这样的边，假设它的终点为v，长度为q。我们就得到一种到u的方式，也就是先走k的距离，到达u，然后再走q的距离，到达v。这样一种方式不一定是最短的，但是，如果这个方式比以前的所有方式都短，我们可以它当作一个"估计距离"。对于其他的点也是一样。也就是，我们的图会成为这个样子：
这个图中，一些黑色的点就是已经确定最短距离的点，而从这些黑色的点到那些蓝色点的距离因为还没有确定下来，所以叫“估计距离"。这个时候，把所有的"估计距离"到达的点中最短的"估计距离"确定为最短距离就可以了，也就相当于算出源点到这个点的距离了。
举个例子，如果上面的u是所有以蓝点为终点的点中"估计距离"离源点最近的，那么就可以把蓝线变成黑线了，相当于确定了1到i到u为从1到u的最短路径。
为什么这个是正确的呢？因为就像刚才到咖啡厅的例子，因为这个估计距离是最短的，所以就不用计算通过其他的点再到这个点的距离了。如果拿刚才的图举例，就是这个样子：
如果u是所有以蓝点为终点的点中"估计距离"离源点最近的，那么这种通过其他的蓝线再经过红线再到达u的路径就应该被舍弃了。因为到达和u同一层的点的时候，距离已经比从1到i到u的长了，就算这些红线再短，也不可能通过它们到u点了。就好比从家到学校再到咖啡厅的距离已经比从家到公园的短了，就不可能通过公园到咖啡厅了。
把一个估计距离确定为最短距离后，需要再按上面的步骤枚举每一条出边，更新其他点的估计距离。然后再重复以上步骤，直到所有的点的最短距离确定下来，运行结束。
概括一下刚才的步骤：
1、把这个图分为两个点集，一个叫S，代表确定最短距离的点集。另一个叫T，代表没有确定最短距离的点集。
2、每个点都有一个值dis[i]，代表源点到它的距离。如果点i在S集合，说明这是它到源点的最短距离。如果在T集合，说明这是它的估计距离。(除源点dis为0之外，开始的无限大)
3、选取T集合里面dis值最小点u的，加入到S集合，相当于计算出源点到u的最短距离。
4、遍历u所有的出边，对于每一条出边和这条出边的终点v，令dis[v]=min(dis[v],dis[u]+这条边长度)，也就是更新所有出边终点的“估计距离”
5、重复3、4步，直到所有的点都加入S集合，算法结束。
好了，现在我们模拟一下这个步骤：
这是数据：
5 6 1 2 5 1 3 8 2 3 1 2 4 3 4 5 7 2 5 2
图呢，长成这个样子：
我们以1为源点，求1到所有点的最短路。
开始，我们先把dis数组赋好初始值，也就是除了dis[1]=0之外，其他的都是无限。
开始，我们先把起点，也就是1号点，加入S集合。然后搜索所有1号点的出边，发现了2号点。从1号点到2号点是5，比原来dis[2]的无限要小，所以更新dis[2]=5，也就是2的估计距离是5。然后发现了3号点，把dis[3]更新为8，也就是其估计距离为8。这时的dis数组是这样的：
dis[0,5,8,∞,∞]
然后，把所有估计距离最小的点加入点集S，也就是2号点加入点集S，确定其最短距离为5。然后搜索所有2的出边，先是5号点，把dis[5]，也就是5号点的估计距离更新为dis[2]+2=7。然后是4号点，把dis[4]更新为8，最后是3号点。本来3号点的估计距离是8，但是dis[2]+1=6,比8小，所以将dis[3]更新为6。
dis[0,5,6,8,7]
然后，再把估计距离最小的3号点加入点集S，确定最短距离为6，然后搜索3的所有出边，发现没有可以更新的。
然后分别是5号点和4号点，依次把它们加入到点集S，确定其最短路径，它们也没有可以更新的。所以算法结束，最后的答案就是：
dis[0,5,6,8,7]
这代表着源点1到所有点的最短路了。
那么具体的代码实现如下(邻接矩阵的)
#include #include #include #include #include #include using namespace std;int map[110][110];//这就是map数组，邻接矩阵存图 int dis[10010];//dis数组，存储估计值int book[10010];//book[i]代表这个点是否再S集合中 int n,m;void dijkstra(int u)//主函数，参数是源点编号{ memset(dis,127,sizeof(dis));//把dis数组附最大值 int start=u;//先从源点搜索 book[start]=1;//把源点加入S集合 for(int i=1;i<=n;i++) { dis[i]=min(dis[i],map[start][i]);//先更新一遍 } for(int i=1;i<=n-1;i++) { int minn=2147483647; for(int j=1;j<=n;j++) if(book[j]==0 && minn>dis[j]) { minn=dis[j]; start=j;//找到T集合中估计距离最近的点 } book[start]=1; //加入S集合 for(int j=1;j<=n;j++) dis[j]=min(dis[j],dis[start]+map[start][j]);//以新的点来更新dis。 }}int main(){ cin>>n>>m; memset(map,127,sizeof(map)); for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; map[a][b]=c; map[b][a]=c; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) map[i][j]=0; dijkstra(1);//以1为源点。 for(int i=1;i<=n;i++) cout<" ";}
运行结果如下：
目前来看，对于每一次把S集合的点移动到T集合，需要枚举每一个节点来找到最小估计距离的点，需要消耗O(n)的时间，而一共要进行n次操作，所以是O(n²)的时间复杂度。
但是，用邻接表来实现的话，可以让时间复杂度减少一些常数。
代码如下：
#include #include #include #include #include #include using namespace std;int value[10010],to[10010],next[10010];int head[10010],total;int book[10010];int dis[10010];int n,m;void adl(int a,int b,int c){ total++; to[total]=b; value[total]=c; next[total]=head[a]; head[a]=total;}void dijkstra(int u){ memset(dis,88,sizeof(dis)); memset(book,0,sizeof(book)); dis[u]=0; for(int i=1;i<=n;i++) { int start=-1; for(int j=1;j<=n;j++) if(book[j]==0 && (dis[start]>dis[j] || start==-1)) start=j; book[start]=1; for(int e=head[start];e;e=next[e])//注意，这里把枚举点便成了枚举start的出边 dis[to[e]]=min(dis[to[e]],dis[start]+value[e]); }}int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; adl(a,b,c); adl(b,a,c); } dijkstra(1); for(int i=1;i<=n;i++) cout<" ";}
运行结果如下：
还可以更加优化吗？在Dijkstra算法中，每次需要找出估计距离最小的节点，这样每次需要消耗O(n)的时间，可不可以把这个过程优化？可以考虑用优先队列。
优先队列，就是一个类似于队列的STL数据结构，可以对内元素进行排序。
当我们更新一个点的估计距离时，我们把它放进一个优先队列中。这样，优先队列的队首永远是估计距离最小的点，每次只需要取队首元素就可以了。
代码实现如下：
#include #include #include #include #include #include #define N 100010using namespace std;int total,head[N],nxt[N<<1],val[N<<1],to[N<<1];int n,m,dis[N],book[N];void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ;}struct node{//重载运算符，便于比较 int dis,index; bool operator < (const node& a) const{ return dis > a.dis; }}P[N];priority_queue Q;void Dijkstra(){ memset(dis,127,sizeof(dis)); dis[1]=0; Q.push(node{0,1}); while(!Q.empty()){ int u=Q.top().index;Q.pop();//取出队首元素，一定是估计距离最小的 if(book[u]) continue; book[u]=1; for(int e=head[u];e;e=nxt[e]) if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; Q.push(node{dis[to[e]],to[e]}); } } return ;}int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; adl(a,b,c); adl(b,a,c); } Dijkstra(); for(int i=1;i<=n;i++) cout<" "; return 0;}
运行结果如下：
优先队列的实现方法是堆，所以其复杂度大约在O(logN)左右。这样整个优先队列优化的Dijkstra复杂度就是O(NlogN)了。
当然，Dijkstra也有它不足的地方。上文曾经说过，当你已知从家到学校再到咖啡厅的距离比从家到公园要小时，就不用考虑从家到公园再到咖啡厅这回事了。但是，有一种情况，是需要考虑的！就是，如果从公园到咖啡厅的距离是负数(是的你没听错)就不能忽略这种情况！这就是图论中的负权边，而这种负权边，也正是Dijkstra解决不了的。想要解决负权边问题，就要看下一篇Bellman-Ford详解了！
在文章的最后，在说点关于笔者名字"Dijkstra"的内容吧。
Dijkstra是一个荷兰名字，它并不符合自然拼读的规律，所以延伸出出很多读法：
1、重音放在"戴"上，k不发音，戴洁斯欻(chua)
2、重音放在”迪"上，k不发音，狄洁斯欻
3、重音放在"迪"上，j不发音，狄克斯欻
4、重音放在"戴"上，戴洁克斯欻
5、重音放在“基"上，狄基克斯欻
6、重音放在”戴"上，j不发音，戴剋(kei)斯欻
至于我为什么选择这个英文名，故事是这样的。我原来英文名叫Jason。在初一那年，去了加拿大的一个夏校，发现和另一个中国同学重名了。而且我觉得这个名字并不是那么高级，于是打算换一个英文名。当时正在学习图论，于是想选一个算法作为英文名。考虑过Floyd，但是因为这个算法时间复杂度太高了，所以没选。又考虑过Tarjan，但是这个名字似乎已经被一个信息竞赛大佬选过了。而且，我总不能叫"Bellman-Ford",这本来就是两个人的名字。最后挑选了Dijkstra。这个名字虽然不符合自然拼读，但是它却很有信息技术色彩。i、j、k是循环常用的变量，str又是string的简称。而且这个名字看起来也十分好看，最终选择了这个名字。
然后，这个名字又给我带来了许多成就。回国后，我创建了一个名叫Dijkstra的博客。又在上面发了一个类似这篇文章的《Dijkstra算法详解》结果因为标题出现了两次Dijkstra，所以只要别人百度上搜Dijkstra，就能在首页看到我的博客。突然间，这篇博客收获了7w多的阅读量，也给予我写更多博客的信心。
言归正传，这篇文章带大家学习了Dijkstra算法，并且证明了它的正确性。还附加了优先队列的优化。在下周的文章中，将介绍Bellman-Ford算法，以解决Dijkstra无法解决的负权边问题。