图的最短路

图的广度优先搜索

在DFS中，一旦发现一个新节点就会立即执行从它开始的递归，这个算法一开始执行就会离源点越来越远，因此称为“深度优先”。这种搜索方式与“栈”后进先出的特性是相同的，我们甚至可以避免递归而用“栈”来实现图的深度优先搜索。

与“后进先出”的栈相对应是“先进先出”的“队列”。把源点推入队列，在队尾推入与源点相连的点，接着我们将队头（此时是源点）从队头推出，然后从队头开始取出结点，每次再把与当前节点相邻且没有访问过的点推入队尾……这种搜索方式称为“广度优先搜索”（BFS）。容易发现，BFS的复杂度也是线性的。

我们尝试用BFS来访问没有边权（边权为1）的图。起初队列里只有源点。之后某个时刻队列中加入了所有与源点距离为1的点，并且弹出了源点本身——此时队列里有且仅有所有到源点距离为1的点。接着我们会依次访问所有这些距离为1的点，并且推入所有与这些点相邻的点。由于所有距离为1的都已经在队列里了，因此所有这些后加入的点到源点的最短距离至少为2。而容易看出2对于这些点来说都是可行的，因此我们证明了接下来被推入的节点到源点的最短距离统统为2。因此一定有某时刻队列里有且仅有的是到源点最短路为2的点……依此类推，我们可以证明我们总能先后找到某时刻队列里仅保存了所有到源点最短距离为\(d\)的点。这说明，BFS的访问顺序可以理解为是以“到源点距离”从小到大一圈一圈访问的。如果我们仿照DFS树的样子画出BFS树，会发现BFS树上节点的深度就是到源点的最短距离。

至此，我们已经在线性时间内解决了单源点的无权图最短路问题。

Dijkstra算法

现在考虑带权的图。我们先讨论边权是正整数的情形。

一个直接的想法是，如果我们把一条权为\(k\)的边拆成\(k\)条权为1的边和\(k-1\)个新的节点，那么问题又转化为了无权图的问题，只需要做BFS就可以求出最短路。但这样做使得复杂度多乘了权的上界这个因子。我们应该看看能不能做得更好——当我们把边拆成小的边之后，我们事实上做了很多无用功，因为我们费力求出了到每个“虚拟点”的最短路，这里面可能存在着冗余之处，给我们提供了优化的空间。

在BFS中，顺序是关键。只要确定了访问的顺序，就可以依据上一轮记录的信息来求出最短路。如果我们能够用某种方法“推断”出上述拆边后的BFS中我们是以怎样的顺序访问各个节点的，也就可以求出最短路了。

我们引入一个“闹钟”来表示我们的“推断”。当我们在拆了边之后的图上从源点出发BFS时，我们知道我们将会的做的就是依次访问所有到源点距离为\(d\)的点。因此我们可以在原图上给所有与源点有直接边的点上，把闹钟设置为边权的大小，代表我们“推测”将会在第\(w_i\)秒到达这个节点。当然，这个推测不一定是对的。但在我们到达任何一个“真的”点之前，一切都在我们的掌控之中。所以，对于边权最小的那个边，我们的推测就一定是对的，闹钟的值就是最短路。此时这个点的BFS要开始走向新的边了，因此必须从这个点出发推测与它相邻的点，并相应地给这些点设置闹钟，如果这次设置的值比之前要小了，那就更新为这次的值。同样的，在下一个闹钟响起之前，一切都是在掌控中的，因为我们完全预测了真正的BFS的运行。因此，下一个响起的闹钟也就是相应节点的最短路……

上面这个设闹钟的做法绝对是正确的，因为它不过是用了一种更省时的方法来模拟BFS。我们现在想从中抽象出我们在数学上到底做了什么。我们对于每个点，用它的边权重新设置了周围点的闹钟。而一旦我们开启时间的运行，我们只关心闹钟时刻最小的那个点——因此如果我们抛弃“闹钟”这一概念，就可以这样描述我们的算法过程：对于当前点\(u\)，访问所有与它相邻的还没有被确定最短路的点\(v\)。如果\(t_u+w(u,v)<t_v\)就用\(t_u+w(u,v)\)更新\(t_v\)。然后，我们从所有未确定最短路的点中选出\(t\)最小的那个，重复上述操作（如果有多个最小值，理论上我们应该同时取出并更新；但实际上没有必要，因为假如有多个最小值，下一个取出的一定是与上一个的\(t\)一样的点）。也可以理解为，每一次我们从所有不在集合\(S\)的点中选出一个\(t\)最小的，用它更新周围的\(t\)，然后把它加入\(S\)。算法结束时，\(S\)内已经包括了所有点，而这些点的\(t\)值就是最短路。

这个算法就是Dijkstra算法，它本质上是BFS的一个推广。从推广的过程中，我们使用时间来模拟边权，这就意味着我们无法保证这一算法对负权边的适用性（事实上，有反例可以证明Dijkstra对负权图是错误的），因为时间是不能倒着走的。但我们能做的推广是把正整数推广到正实数（虚拟点的多少而已）。Dijkstra对正权图是始终正确的。

Dijkstra需要耗费比BFS更多的时间，因为它的取点顺序不是简单地取出队首，而是需要取出“队列”中\(t\)最小的那个点。这样的队列称为“优先队列”。如果我们用枚举来找最小的点，Dijkstra的复杂度是\(O(|V|^2+|E|)\)的。但好在我们已经有数据结构能帮助我们维护“支持插入和删除的集合中的最值”，最常见的就是一种叫“堆”的二叉树，它可以在\(O(\log n)\)的时间内完成插入和删除，\(O(1)\)访问最值。这样，Dijkstra的复杂度就被优化为了\(O((|V|+|E|)\log |V|)\)（每访问一条边都可能会进行依次更新，更新就等价于堆上的插入，因此\(|E|\)被移进了括号内）。