C＋图进阶系列之 Bellman-Ford和Dijkstra 最短路径求解算法

1. 前言

因无向、无加权图的任意顶点之间的最短路径由顶点之间的边数决定，可以直接使用原始定义的广度优先搜索算法查找。

但是，无论是有向、还是无向，只要是加权图，最短路径长度的定义是：起点到终点之间所有路径中权重总和最小的那条路径。

如下图所示， 到 的最短路径并不是直接到 （权重是），而是 到 再到 （权重是 ）。所以，需要在广度优先搜索算法的基础上进行算法升级后才能查找到。

加权图的常用最短路径查找算法有：

贝尔曼-福特（Bellman-Ford）算法。

Dijkstra（迪杰斯特拉） 算法。

算法。

算法。

本文重点介绍 和算法。

2. 贝尔曼-福特（）算法

算法取自于创始人和，本文简称 算法

算法属于迭代、穷举算法，算法效率较低，如果图结构中顶点数量为 ，边数为 ，则该算法的时间复杂度为 ，还是挺大的。

理论上讲，图结构中边上的权重一般用来描述现实世界中的速度、时间、花费、里程……基本上都是非负数。即使是负数， 算法也能工作得较好。

2.1 BF 算法思想

问题描述：如下图，搜索 到其它任意顶点之间的最短路径。

首先给每一个顶点一个权重值（用来存储从到的最短路径上所有边上权重之和），刚开始除了出发点的权重 0 ，因为还不能确定到其它任意顶点的具体路径长度，其它顶点的权重值均初始为无穷大（只要是一个适当值都可以）。

下面的图结构是，对于同样适用 算法。

算法流程

更新顶点的权重： 计算任一条边上一端顶点（始点）到另一个端顶点（终点）的权重。新权重=顶点（始点）权重+边的权重，然后使用新权重值更新终点的原来权重值。

更新原则： 只有当顶点原来的权重大于新权重时，才更新。

先选择 之间的路径，因为 是无向边，需要计算 次。如果是有向图，则只计算一个方向。

先计算 的新权重=的权重+（，）边上的权重，新权重=。因 小于 顶点现在的权重（无穷大）， 的权重被更新为 。

再计算 的新权重=的权重+(，) 边上的权重。新权重=。 大于 现有的权重 0，则 顶点不更新。

Tips： 此时，意味着 的最短路径长度为 。** 是 的前序顶点。** 但是，这绝对不是最后的结论。

对图中每一条边两端的顶点都执行上述同样的操作，对于执行顺序没有特定要求。如下继续计算 边的两端顶点的权重。

的新权重=，更新 顶点权重为 。

的新权重= 不更新。结论： 是 的前序顶点。

Tips： 当顶点的权重更新后，也意味着前序顶点也发生了变化。如上述权重更新过程中 刚开始前序是 ，后来又更改成了 。

计算   权重：

 的新权重=，小于 现有权重 ， 的权重更新为 ，则 B 是 C的前序顶点

的新权重= ，大于 现有权重，不更新。

经过上述操作后 3 个顶点的前序关系： 是 的前序、 是 的前序，当前  的最短路径是 ， 的最短路径是 ，但不一定是最后结论。

当所有边两端顶点都更新完毕后，需要再重新开始，对图结构中所有边上的顶点权重再进行一次更新，一直到不再引起权重变化时 算法才算结束。

算法的本质还是广度优先搜索算法，附加了更新顶点权重的逻辑。

2.2 结构设计

在实现算法之前，先要为图设计一系列类型。

2.2.1  顶点类型

此类用来描述顶点本身信息，除了有顶点的常规属性，如编号、名称、链接表……外，还需要添加 个属性：

顶点的权重：初始化时为无穷大。

Tips:  顶点权重用来保存起始点到此顶点的最短路径长度（边上权重之和）。

前序顶点： 在 算法中，如果顶点的权重发生了更新，也意味着前序顶点也发生了变化。

基本结构：

继续在顶点结构体中添加如下的函数，满足对顶点的一系操作。

添加相邻顶点函数

顶点对象以字符串格式输出

更新顶点权重函数

此函数为 算法的核心子逻辑，参数 是指与当前顶点相邻的顶点。先是计算和当前顶点的新权重，根据更新原则进行更新。如果有更新则需要把当前顶点指定为前序顶点。

Tips： 在图结构中，最短路径算法中的前序顶点指到达此顶点最近的顶点。

重载函数

2.2.2 图类

此类用来对图中的顶点进行维护，如添加新顶点，维护顶点之间的关系、提供 搜索算法……

图类的基本结构

其它功能函数

查询函数: 有 个，一个按值在图中查询单个顶点，一个在图中查询所有顶点。

添加新顶点以及维护顶点之间的关系函数： 新顶点的编号由内部提供，统一管理，保证编号的一致性。

贝尔曼-福特算法：  这里用到了递归，在  算法中，一轮更新后可能还需要后续多轮更新才能让每一个顶点上的权重不再变化。这也是 算法的缺陷。

输出最短路径函数： 先计算，再输出。

测试图类中的函数：

添加顶点以及顶点之间的关系：

测试结果：

算法测试

输出结果：

如下图，路径中最后一个顶点的就是起点到此顶点的最短路径值(路径权重)。

3. （迪杰斯特拉）算法

算法() 是由荷兰计算机科学家于1959 年提出的，因此又叫。为了便于表述，本文简称 算法。

算法和前面所聊的 算法，可谓同工异曲，算法的核心思想是相同的：

搜索到某一个顶点后，更新与其相邻顶点的权重。

Tips： 权重计算法则以及权重更新原则两者相同。

且顶点权重的数据含义和 算法的一样。表示从起始点到此点的最短路径长度（也就是经过的所有边的权重之和）。

Tips： 初始时，因还不能具体最短路径，起始点的权重为 ，其它顶点权重可设置为无穷大。

算法相比较 算法有 个不同的地方：

在无向加权图中， 算法需要对相邻 个顶点进行双向权重计算。

算法搜索时，每次选择的下一个顶点是所有权重值最小的顶点。其思想是保证每一次选择的顶点和当前顶点权重都是最短的。所以，是基于贪心思想。

3.1 算法流程

如下图结构中，查找 到任一顶点的最短路径：

定位到起始点 ， 顶点也称为。

设置 的权重为 ， 的相邻顶点有 和 ，需要计算 到 以及 到 之间的权重。这里是先选择 还是 并不重要。先选择 顶点，计算 的路径长度权重。新权重计算公式＝顶点权重＋边的权重＝０＋３＝３．

更新原则和 算法一样，当计算出来的权重值小于相邻顶点的权重值时，更新。于是 的权重更新为 ．此时 是 的前序顶点。

再选择  顶点，计算 路径长度权重＝，因 小于 现在的无穷大权重， 的权重被更新为 。

Tips： 到这里， 可以说 算法和 算法没有什么不一样。

但是， 算法不需要对边上 个顶点进行双向权重计算，这是 算法与 算法的第一个差异性。

此时，更新后的图结构如下所示:

很显然， 和 将成为下一个搜索的候选点，这里 算法和 算法就有了很大的差异性。

算法对于选择 还是 的顺序没有要求。

算法则不同，会选择 和 中权重值更小的那个， 的权重 3 小于 的权重 9 ，当然选择 为下一个搜索顶点。

这是 BF 算法和 DJ 算法的第二个差异性！

选择 后也就意味着 之间的最短路径就确定了。为什么？

因你无法再找出一条比之更短的路径。

这里也是 算法的关键思想，在选择一个权重最小的候选顶点后，就能确定此顶点和它的前序顶点之间的最短路径长度。

Tips： 到现在为止， 的前序顶点是 ； 的前序顶点也是 。

因为 已经被选为下一个搜索顶点，于是 顶点和它的前序顶点 之间的最短路径已经出来了。

A－＞Ｂ　最短路径长度为 ３。

因 顶点还没有成为搜索顶点，其和 顶点之间的最短路径还是一个未知数。

**Ｂ成为当前顶点 **

找到与 相邻的 、、  个顶点，然后分别计算路径长度权重。 的新权重=３+4＝７ 小于 现有的权重  ９ ，C 的权重被更新为 ７ ，C 的前序顶点也变成了 B。

同理， 路径中 的权重被更新为 5； 路径中 的权重被更新为 ６ 。

再在 、 、  个顶点中选择权重值最小的 为下一个搜索顶点．到这里！可以发现 算法和原始定义的广度搜索算法以及 之间就有了本质上的区别：

广度优先搜索算法会选择和 同时进入队列的   顶点成为下一个搜索顶点。因为 和  都是离 较近的顶点。

而 算法是在候选顶点中，哪一个顶点的权重最少，就选择谁，不采用就近原则．而是以顶点的权重值小作为优先选择条件．

Tips： 选择 后 ，各顶点间的关系：

的前序是 ，间最短路径已经确定。

的前序是 ，间的最短路径可以确定，又因为 的前序顶点是 ，所以 的最短路径可以确定。

其它项点间的最短路径暂时还不明朗。

D 顶点为当前顶点

计算与 相邻的 顶点的权重。

的新权重= 大于 现有权重 ，不更新。** 的前序顶点还是 。**

的新权重= ， 的权重由无穷大更新为 。

再在剩下的所有可选顶点中选择权重值小的 顶点为下一个搜索点，当选择 后：

Tips：  的前序为 , 的前序是 ，所以 到 的最短路径长度就是 ，路径长度为 。

E 为当前顶点，计算和其相邻顶点间的权重。

唯一可改变的是 顶点的权重， 顶点的前序顶点变为 。

再选择 C 为当前顶点

和相邻顶点不会再产生任何权重的变化，其前序顶点还是 。所以 到 之间的最短路径应该是 路径长度为 。

最后选择 顶点，也不会再产生任何权重变化， 的前序是 ，的前序是，的前序是，所 到 的最短路径应该是 权重值为 。

最后，以图示方式，比较 算法和 算法中各顶点出队列的顺序。 采用就近原则出队列，然后不停计算相邻顶点的权重，直到权重不再变化为止，显然用的是蛮力， 采用权重值小的优先出队列，显然用的是巧力。

3.2 编码实现

分析完 DJ 算法流程，准备编码

和上面的 算法相比较，顶点类一样，在图类中添加 算法。

算法的本质还是广度优先搜索算法，有所区别的地方是使用优先队列，每次从队列中选择顶点时，选择顶点权重最小的。

所以需要在类中添加优先队列对象，并为队列提供用于比较的函数对象。

** 算法函数**

测试代码：

输出结果：和前面的结论一样。

算法不适合用于边上权重为负数的图中，否则可能找不到路径。

3. 总结

在加权图中查找最短路径长度算法除了 、 算法，还有  、  算法。有兴趣的可以自行了解。