「编程笔记」Dijkstra算法为什么无法处理带有负权边的图

前言

Dijkstra算法是一种可以计算有向或无向图中单源最短路的算法。其工作模式与图的BFS（广度优先遍历）有些相似，通过类似于广度遍历的方式，逐渐从某个设定好的起点向外推进，一步步的计算出所有点到该点的距离。

本文不过多介绍Dijkstra单源最短路算法本身，如果仍然没有掌握该算法，可以先自行了解该算法的工作模式。下面提供一些可供参考的资料：

知乎：通俗易懂理解——dijkstra算法求最短路径

负权边对于Dijkstra算法的影响

Dijkstra算法工作模式

要了解该影响，首先需要明确Dijkstra算法的工作模式。其维护两个点集合。一个是“仍未确定最优解的点（S）”，一个是“已经确定最优解的点（U）”。且有一个重点：在算法工作期间内，如果某点被认为已经得到最优解，则该点会被从S移动到U，可以认为，从此以后该点已经被Closed（关闭），即解已经确定，且不容被更改。

为了方便，我们称在S中的点为opening vertex，U中的点为closed vertex

当图中出现负权边…

了解这一点后，让我们来看看下面这个图片示例，看看当负权边出现在图中时，可能会对算法造成什么影响：

如上图，假设我们尝试使用Dijkstra算法，计算该图中各个点距离C点的距离。

图中，绿色的点为closed vertex，白色的点为opening vertex，点上方的方框代表该点的，实时更新的计算距离。

1：算法首先锁定C点，将C点到C点的距离标记为0，并认定为最优解，然后根据C点尝试更新与其相连的opening vertex的距离（这里为A，B点，得到更新后距离是为1和5）。

2：剩余的opening vertex中，A距离出发点（C点）最小，距离为1，故锁定A点，（注意：锁定A点说明算法认为A点的最优解就是1，且之后算法也不可能再次更新A点的距离值，因为A点已经为Closed状态了），同时，锁定A点之后，再次更新与A点相连的opening vertex的值（与A点相连的点有B和C，但因为C点为closed vertex，故仅仅尝试更新B点的值），计算得到B点最新距离为min(5, 1+(-10)) = -9

3：最后，锁定B点，算法计算完成。

上方便是Dijkstra算法在示例图中的运行步骤和结果。不难发现，算法对于A点的最短距离出现了计算失误：实际上，A点的最短距离走法并不是C->A (1)，而是C->B->A (-5)。

怎会如此？

分析之后可以发现，Dijkstra算法的核心，就在于每次都选择S集合中距离最小的点，并将其锁定，再通过这个点进一步更新其他点的距离。但为什么Dijkstra认为S集合中目前距离最小的点就是最优解呢？有没有可能从其他的点出发可以得到更小的距离呢？

比如在上述的示例图中，锁定C点后，算法认为A点的距离是1，B点的距离是5，所以A点的距离为1一定是最优解。那么有没有可能实际上1并不是C到A的最优解，我们通过B点走其他的路径最终可以得到更小的解呢？

答案是，当边的权值非负时，不可能，当边的权值存在负值时，则有可能。

当权值非负时，B点已经离出发点有5点的距离，所以所有从出发点出发经B点的路径，其长度必定大于等于5，但是当权值存在负数的时候，这一点就无法确定，经过B点的路径如果后续经过负权边，其路径长度总和也有可能再次小于5，此时，我们就无法确定C->A的1距离一定是最优解了，因为我完全有可能经由B路径得到一条总距离小于1的路径到达A。

上方的论证可能并不全面和严谨，不能作为Dijkstra算法相关特性的严格证明，但对我们进一步理解Dijkstra算法有着一些帮助。

一些有趣的说法

不难发现，实际上Dijkstra算法的设计和「贪心」有着很大的联系，实际上在S集合中选点就是一种贪心的行为。而我们都知道贪心算法的局限性，就是在部分情况下，其可能陷入局部最优解。而我们可以认为，当Dijkstra遇上负权边，就导致了其中贪心部分陷入了局部最优解（只考虑眼前的最短边（比如在5和10两条边中毫不犹豫的选择5），而忽略了目前看似落后的边未来的长期收益（比如那条权值为10的边链接的点，接下来将经过一条绝对值非常大的负权边-10000之类的），这也警示我们不要贪图眼前的小利，眼光应当长远（雾

如果我就是想拿下负权边呢？

噢亲爱的读者，相信我，不止你一个人有这种想法；实际上上百年前就已经有两名小伙想要拿下他，他们的名字分别是Richard Bellman 和Lester Ford Jr，接下来，就是Bellman Ford算法的表演时间了。

如果你对与这个Bellman Ford算法感兴趣，可以在互联网上找到很多关于这个算法的优质教程，其通过一次次迭代，对边进行Relaxation操作，实现了对于单源最短路径的求解，在本Blog的另外一篇文章「编程笔记」关于Bellman Ford单源最短路算法 中，也对这个算法做出了一些讨论，希望能对您产生一些帮助和启发。