Patrick教授希望找到一条从菲尼克斯(Phoenix)到印第安纳波利斯(Indianapolis)的最短路径。给定一幅美国的道路交通图，上面标有所有相邻城市之间的距离，Patrick教授怎样才能找出这样一条最短的路径呢?

一种可能的办法当然是，先将从菲尼克斯到印第安纳波利斯的所有路径都找出来，将每条路径上的距离累加起来，然后选择其中最短的路径。但是，即使在不允许环路的情况下，也可以看得出来，Patrick教授需要检查无数种可能的路径，而其中的大多数路径根本不值得检查。例如，一条从菲尼克斯经过西雅图再到印第安纳波利斯的路径显然不符合要求，因为西雅图已经偏离了目标方向好几百英里。

最短路径问题 权重 最短路径权重 最短路径

在求取从菲尼克斯到印第安纳波利斯的最短路径的例子中，我们可以用一幅图来表示道路交通图:结点代表城市，边代表城市之间的道路，边上的权重代表道路的长度。我们的目标就是找出一条从给定城市菲尼克斯到给定城市印第安纳波利斯的最短路径。

当然，边上的权重也可以代表非距离的度量单位，如时间、成本、罚款、损失，或者任何其他可以随路径长度的增加而线性积累的数量以及我们想要最小化的数量。

22.2节讨论的广度优先搜索算法就是一个求取最短路径的算法，但该算法只能用于无权重的图，即每条边的权重都是单位权重的图。由于许多广度优先搜索的概念来源于对带权重的图的最短路径的研究，读者可能需要先复习22.2节的内容，再继续本章的学习。

本章概要

• 24.1节对 Bellman-Ford算法进行讨论。该算法解决的是一般情况下的单源最短路径问题。在一般情况下，边的权重可以为负值。Bellman-Ford算法非常的简单，并且还能够侦测是否存在从源结点可以到达的权重为负值的环路。
• 24.2节将给出在有向无环图中计算单源最短路径的线性时间的算法。
• 24.3节讨论Dijkstra算法。该算法的时间复杂度低于Bellman-Ford算法，但却要求边的权重为非负值。
• 24.4节描述如何使用Bellman-Ford算法来解决线性规划中的一种特殊情况。
• 24.5节将对上面陈述的最短路径和松弛操作的性质予以证明。

24.1 Bellman-Ford算法

BELLMAN-FORD(G,w,s)

INITIALIZE-SINGLE-SOURCE(G,s)
for i = 1 to |G.V| - 1
	for each edge(u,v)∈G.E
    	RELAX(u,v,w)
for each edge(u,v)∈G.E
	if v.d > u.d + w(u.v)
    	return FALSE
return TRUE

图 24-4 Bellman-Ford算法的执行过程

要证明Bellman-Ford算法的正确性，首先证明在没有权重为负值的环路的情况下，该算法正确计算出从源结点可以到达的所有结点之间的最短路径权重。

引理 24.2

证明

推论 24.3

定理 24.4 Bellman-Ford算法的正确性

证明

练习

24.1-4

Solution

BELLMAN-FORD'(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    for i = 1 to |G.V| - 1
        for each edge (u, v) ∈ G.E
            RELAX(u, v, w)
    for each edge(u, v) ∈ G.E
        if v.d > u.d + w(u, v)
            mark v
    for each vertex v ∈ marked vertices
        FOLLOW-AND-MARK-PRED(v)

FOLLOW-AND-MARK-PRED(v)
    if v != NIL and v.d != -∞
        v.d = -∞
        FOLLOW-AND-MARK-PRED(v.π)
    else
        return

在运行BELLMAN-FORD′之后，使用负权重循环上的所有顶点作为源顶点运行DFS。从这些顶点可以到达的所有顶点的d属性都应设置为−∞。