最短路径问题
在图结构中，求解最短路径问题有多种算法，Bellman-Ford 是其中之一，它可以处理含有负权边的情况，同样是单源最短路径算法，而之前讲到的 Dijkstra 算法不能处理含有负权边的情况。对应的代价就是其算法时间复杂度要高一些。后面我们会分析。
这里能处理负权边是针对有向图的，因为对无向图来说，含有负权边就意味着含有负权回路，在有负权回路的这种情况下求最短路径是无解的，因为每经过一次负权回路，距离都会减少，就会无限循环下去。
在继续往下讲之前，先补充一个图最短路径的一个性质：最短路径的子路径也是最短路径，数学描述如下：有向图 G =(V,E)G=(V,E)G=(V,E)，设 p =(v0,v1,…,vk)p=(v_0,v_1,…,v_k)p=(v
0
,v
1
,…,v
k
)为从点 v0v_0v
0
到点 vkv_kv
k
的一条最短路径，且 0≤i≤j≤k0≤i≤j≤k0≤i≤j≤k，设 pij=(vi,vi+1,…,vj)p_{ij}=(v_i,v_{i+1},…,v_j)p
ij
=(v
i
,v
i+1
,…,v
j
)为路径 ppp 中从点 viv_iv
i
到点 vjv_jv
j
的子路径，那么 pijp_{ij}p
ij
也是这两点之间的一条最短路径。可用反证法来证明：
证明：如果将路径 ppp 分解为 v0−vi−vj−vkv_0-v_i-v_j-vkv
0
−v
i
−v
j
−vk，则有 w(p)=w(p0i)+w(pij)+w(pjk)w(p)=w(p_{0i})+w(p_{ij})+w(p_{jk})w(p)=w(p
0i
)+w(p
ij
)+w(p
jk
)。假设存在一条从 viv_iv
i
到 vjv_jv
j
的一条更短的路径 p′ijp_{ij}’p
ij
′
，w(p′ij<w(pij))w(p_{ij}'<w(p_ij))w(p
ij
′
<w(p
i
j))。则新路径权值为 w(p0i)+w(p′ij)+w(pjk)<w(p)w(p_{0i})+w(p_{ij}’)+w(p_{jk}) < w(p)w(p
0i
)+w(p
ij
′
)+w(p
jk
)<w(p)，这与 ppp 是最短路径相矛盾。
Bellman-Ford 算法
与 Dijkstra 算法类似，Bellman-Ford 算法也是通过不断的“松弛”操作来求得最终解。“松弛”就是如下的操作过程：w(u,v)w(u,v)w(u,v)表示 uuu 与 vvv 之间的权值，d[v]d[v]d[v]表示从源点 sss 到顶点 vvv 的距离，若存在边 e(u,v)e(u,v)e(u,v)，使得：d[v]>d[u]+w(u,v)d[v] > d[u] + w(u,v)d[v]>d[u]+w(u,v)(即发现了优于当前的路径), 则更新 d[v]=d[u]+w(u,v)d[v] = d[u] + w(u,v)d[v]=d[u]+w(u,v)，并更新路径 prev[v]=uprev[v] = uprev[v]=u。可以看到每一次“松弛”都会更逼近最优解。Dijkstra 算法通过优先队列每次选择当前未被处理过的距离最小的顶点，对该顶点未被处理过的边进行松弛。而 Bellman-Ford 算法则简单的松弛所有的边，反复执行∣V∣−1|V|-1∣V∣−1 次（∣V∣|V|∣V∣为顶点的的个数），时间复杂度 O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。可以看出，Bellman-Ford 松弛的次数远多于 Dijkstra，所以其时间复杂度相比 Dijkstra 要高。
伪代码如下：
function BellmanFord(list vertices, list edges, vertex source)
// step 1 初始化, dist[v]表示源节点到顶点 v 的距离值，prev[v]表示顶点 v 的前驱顶点
for each vertex v in vertices
dist[v] = inf
prev[v] = null
dist = 0
// step 2 迭代松弛 |V|- 1 次
for i from 1 to size(vertices) -1
for each edge(u,v) with weight(u,v) in edges
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v)
prev[v] = u
// step 3 检查是否有负权回路
for each edge(u,v) with weight(u,v) in edges
if dist[u] + weight(u,v) < dist[v]
error "检测到负权回路"
return dist[], prev[]对算法的优化：在实际应用中，Bellman-Ford 算法其实不用迭代松弛∣V∣−1|V|-1∣V∣−1 次，理论上图中存在的最大的路径长度为∣V∣−1|V|-1∣V∣−1，实际上往往要小于这个∣V∣−1|V|-1∣V∣−1，即，在∣V∣−1|V|-1∣V∣−1 次迭代松弛之前就已经收敛了，计算出最短路径了，所以可在循环中设置判定，在某次循环中不再进行松弛时，表明当前已收敛，可退出步骤 2，进行下一步检查是否有负权回路。
怎么理解这个算法呢？假设某顶点与源顶点没有连通，即没有边，那么这个点就不会被松弛，距离不会被更新，依旧为无穷大。如果顶点与源顶点是连通的，在不存在负权回路的情况下，一定存在一条最短路径，这条最短路径 p =(v0,v1,…,vk)p=(v_0,v_1,…,v_k)p=(v
0
,v
1
,…,v
k
)为源点 sss 到 vvv 之间的任意一条最短路径 (这里 v0=sv_0=sv
0
=s，vk=vv_k=vv
k
=v)。最大会有多少条边呢？假设图有∣V∣|V|∣V∣个顶点，那么有 k≤∣V∣−1k≤|V|-1k≤∣V∣−1。在进行第一轮松弛时，被松弛的边中一定会包含边(v0,v1)(v_0,v_1)(v
0
,v
1
)，结合文章开头讲到的最短路径的子路径也一定是最短路径的性质，v1v_1v
1
已经得到了其最短路径，在第二轮松弛过程中，被松弛的边中一定会包含边(v1,v2) 边(v_1,v_2)边(v
1
,v
2
)，经过此次松弛后，v2v_2v
2
也已经得到了其最短路径。以此类推，在第 kkk 轮松弛中，被松弛的边中一定包含了边(vk−1,vk)(v_{k-1},v_k)(v
k−1
,v
k
)，之后 vkv_kv
k
也得到其最短路径。也就是说，凡是与源顶点最短路径经过的边数为 kkk 的顶点，在第 kkk 轮松弛时一定会被确认（最短路径被找到）。所以，我们需要松弛多少轮呢，最多∣V∣−1|V|-1∣V∣−1 次就可以了。
算法的数学证明可以参考《图论》或《算法导论》中的证明过程。
代码实现见 bellman_ford.cpp。最后再分析一下时间复杂度，最坏的情况 O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)，这个比较好理解，最好的情况 O(∣E∣)O(|E|)O(∣E∣)，一次松弛所有边的操作就可以了，对应的就是边松弛的顺序恰好是最短路径树的生成顺序。
算法的应用
其中一个应用就是路由协议了（距离向量协议），对此实现了一个路由协议测试工程，代码见 router。实现了一个通过路由表的方式进行的路由算法。