1、在最短路径问题中，给定一个带权重的有向图 G = (V, E) 和权重函数 w: E→R ，该权重函数 将每条边映射到实数值的权重上。图中一条路径 p =〈v0, v1, …, vk〉 的权重 w(p) 是构成该路径的 所有边的权重之和：
定义从结点 u 到结点 v 的最短路径权重 δ(u, v) 如下：
从结点 u 到结点 v 的最短路径则定义为 任何一条权重为 w§ = δ(u, v) 从 u 到 v 的路径 p
2、22.2 节讨论的广度优先搜索算法 就是一个求取最短路径的算法，但该算法 只能用于无权图，即每条边的权重 都是单位权重的图
3、最短路径的几个变体
讨论 单源最短路径问题：给定一个图 G = (V, E)，希望找到从给定源结点 s ∈ V 到每个结点 v ∈ V 的最短路径
单目的地 最短路径问题：找到从每个结点 v 到给定目的地结点 t 的最短路径。如果 将图的每条边的方向翻转过来，就可将这个题转换为单源最短路径问题
单节点对最短路径问题：找到从给定结点 u 到给定结点 v 的最短路径。如果 解决了针对单个结点 u 的单源最短路径问题，那么也就解决了这个问题。而且，在该问题的所有已知算法中，最坏情况下的渐近运行时间 都和最好的单源最短路径算法的运行时间一样
所有节点对 最短路径问题：对于每对结点 u 和 v，找到从结点 u 到结点 v 的最短路径。虽然 可以针对每个结点运行一遍单源最短路径算法，但通常可以更快地解决这个问题
4、最短路径的最优子结构
最短路径算法 通常依赖于最短路径的一个重要性质：两个结点之间的一条最短路径 包含着其他的最短路径。最优子结构 是可以使用动态规划（第 15 章）和贪心算法（第 16 章）的一个重要指标。Dijkstra 算法就是一个贪心算法，而 Floyd-Warshall 算法则是一个动态规划算法，该算法 能够找出所有节点对之间的最短路径
引理 24.1 （最短路径的子路径也是最短路径）
给定带权重的有向图 G = (V, E) 和权重函数 w: E->R。设 p = <v_0, v_1, …, v_k> 为从起点 v_0 到终点 v_k 的一条最短路径，并且对于任意的 i 和 j，0 <= i <= j <= k，设 p_ij = <v_i, v_{i+1}, …, v_j> 为路径 p 中从节点 v_i 到节点 v_j 的子路径。那么 p_ij 是从节点 v_i 到节点 v_j 的一条最短路径
5、如果图 G 包括从 s 可以达到的权重为负值的环路（可达+环路权重为负），则最短路径权重无定义。从 s 到该环路上的任意结点的路径 都不可能是最短路径，因为 可以沿着任何“最短”路径 再经历一次权重为负值的环路，则总是可以找到一条权重更小的路径
因为环路 <e, f, e> 的权重为 3 + (−6) = −3 < 0，从结点 s 到结点 e 没有最短路径。通过经历 负权重环路 <e, f, e> 任意次数，可以找到 权重为任意负值的 从结点 s 到结点 e 的路径，因此 δ(s, e) = −∞。类似地，δ(s, f) = −∞。因为结点 g 可以从结点 f 到达，可以找到 一条权重为任意负值的 从结点 s 到结点 g 的路径，因此 δ(s, g) = −∞。结点 h、i 和 j 也形成一个权重为负值的环路，但它们不能从结点 s 到达，因此 δ(s, h) = δ(s, i) = δ(s, j) = ∞
某些最短路径算法（如Dijkstra算法）假设输入图的所有边权重为 非负值。另外一些算法（如Bellman-Ford算法），允许输入图中包含 负权重的边。但只要 没有可以 从源结点到达的权重为负值的环路，就可以生成正确的答案。在通常情况下，如果存在一条权重为负值的环路，Bellman-Ford 算法可以侦测并报告其存在
6、环路
最短路径 也不能包含权重为正值的环路，因为 只要将环路从路径上删除 就可以得到一条源结点和终结点与原来路径相同的 一条权重更小的路径
只要一条最短路径上 还有权重为 0 的环路，就可以 重复删除这些环路，直到得到 一条不包括环路的最短路径。因此，不失一般性，可以假定 在找到的最短路径中没有环路，即它们都是简单路径。由于图 G = (V，E) 中的任意无环路径 最多包含 |V| 个不同的结点，它也最多包含 |V| - 1 条边。因此，可以将注意力集中在 至多只包含 |V| - 1 条边的最短路径上
7、最短路径的表示
不但希望 计算出最短路径权重，还希望 计算出最短路径上的结点。对最短路径的表示 与 22.2节中对广度优先搜索树的表示相似。给定图 G = (V，E)，对于每个结点 v，维持一个前驱结点 v.π。该前驱结点 可能是另一个结点 或者 NIL。本章的最短路径算发将对每个结点的 π 属性进行设置，这样，将从结点 v 开始的前驱结点链反转过来，就是从 s 到 v 的一条最短路径
在运行最短路径算法的过程中，π 值并不一定能给出最短路径（算法尚未完成、存在负权重环 或 存在多条最短路径的情况）
由 π 值所诱导的前驱子图 Gπ = (Vπ, Eπ)。定义结点集 Vπ 为图 G 中的前驱结点不是 NIL 的结点的集合，再加上源结点 s，即
有向边集合 Eπ 是由 Vπ 中的结点的 π 值所诱导的边的集合，即
在算法终止时，Gπ 是一棵最短路径树。非形式化地说，最短路径树 是一棵有根结点的树，该树包括了 从源结点 s 到每个可以从 s 到达的结点的一条最短路径。一棵最短路径树 有点类似于 22.2 节中的广度优先树，但它所包括的最短路径 是以边的权重来定义的，而不是 边的条数
更准确地说，设 G = (V, E) 是一棵带权重的有向图，其权重函数为 ω:E→R，假定 G 不包含从 s 可以到达的权重为负值的环路，因此，所有的最短路径都有定义。一棵根结点为 s 的最短路径树 是一个有向子图 G′ = (V′, E′)，这里V′⊆V，E′⊆E，满足：
- V′ 是图 G 中从源结点 s 可以到达的所有结点的集合
- G′ 形成一棵根结点为 s 的树
- 对于所有的结点 v ∈ V′，图 G′ 中从结点 s 到结点 v 的唯一简单路径是 图 G 中从结点 s 到结点 v 的一条最短路径
最短路径不一定是唯一的，最短路径树也不一定唯一
8、松弛操作
对于每个结点 v 来说，维持一个属性 v.d，用来记录从源结点 s 到结点 v 的最短路径 权重的上界。称 v.d 为 s 到 v 的最短路径估计。使用下面运行时间为 Θ(V) 的算法 来对最短路径估计和前驱结点进行初始化：
INITIALIZE-SINGLE-SOURCE(G,s)
1 for each vertex v in G.V
2 v.d = ∞
3 v.π = NIL
4 s.d = 0
对一条边 (u，v) 的松弛过程为：首先测试一下 是否可以对 s 到 v 的最短路径进行改善
测试的方法是，将从结点 s 到结点 u 之间的最短路径距离 加上结点 u 与 v 之间的边权重，并与当前的 s 到 v 的最短路径估计进行比较，如果前者更小，则对 v.d 和 v.π 进行更新。松弛步骤 可能降低最短路径的估计值 v.d 并更新 v 的前驱属性 v.π
对边 (u，v) 在 O(1) 时间内进行的松弛操作 :
RELAX(u,v,w)
1 if v.d > u.d + w(u,v)
2 v.d = u.d + w(u,v)
3 v.π = u
本章的每个算法 都将调用算法 INITIALIZE-SINGLE-SOURCE，然后重复对边进行松弛。而且，松弛 是唯一导致最短路径估计和前驱结点发生变化的操作。Dijkstra 算法 和 用于有向无环图的最短路径算法 对每条边仅松弛一次。Bellman-Ford 算法则对每条边松弛 |V| - 1 次
9、最短路径 和 松弛操作的性质
成立的前提是 必须调用 INITIALIZE-SINGLE-SOURCE(G, s) 来对图进行初始化，并且 所有对最短路径估计 和 前驱子图所做的改变 都是通过一系列的松弛步骤 来实现的
三角不等式性质 (引理 24.10) 对于任何边 (u, v) ∈ E，我们有 δ(s, v) ≤ δ(s, u) + w(u, v)
上界性质 (引理 24.11) 对于所有的结点 v ∈ V，总是有 v.d ≥ δ(s, v)。一旦 v.d 的取值达到 δ(s, v)，它的值将不再发生变化
非路径性质 (推论 24.12) 如果从结点 s 到结点 v 之间不存在路径，则总是有 v.d = δ(s, v) = ∞
收敛性质 (引理 24.14) 对于某些结点 u, v ∈ V，如果 s → u → v 是图 G 中的一条最短路径，并且在对边 (u, v) 进行松弛前的任意时间有 u.d = δ(s, u)，则在之后的所有时间有 v.d = δ(s, v)
路径松弛性质 (引理 24.15) 如果 p = <v0, v1, …, vk> 是从源结点 s = v0 到结点 vk 的一条最短路径，并且 对 p 中的边所进行松弛的次序为 (v0, v1), (v1, v2), …, (vk-1, vk)，则 vk.d = δ(s, v_k)。该性质的建立 与任何其他的松弛操作无关，即使这些松弛操作是与对 p 上的边所进行的松弛操作穿插进行的
前驱子图性质 (引理 24.17) 对于所有的结点 v ∈ V，一旦 v.d = δ(s, v)，则前驱子图是 一棵根结点为 s 的最短路径树
所有算法 都假设有向图 G 以邻接链表的方式予以存放。此外，边的权重与边本身存放在一起，这样在遍历每条邻接链表时，可以在 O(1) 时间内获得边的权重
1、Bellman-Ford 算法
1、Bellman-Ford 算法 解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。给定带权重的有向图 G = (V, E) 和权重函数 w: E→R，Bellman-Ford 算法返回一个布尔值，以表明 是否存在一个从源结点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们 不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重
Bellman-Ford 算法 通过对边进行松弛操作 来逐渐地降低从源结点 s 到每个结点 v 的最短路径的估计值 v.d，直到该估计值与实际的最短路径权重 δ(s, v) 相同时为止。该算法返回 TRUE 值 当且仅当输入图不包含可以从源结点到达的权重为负值的环路
BELLMAN-FORD(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 for i to |G.V|-1
3 for each edge(u,v)in G.E
4 RELAX(u,v,w)
5 for each edge(u,v)in G.E
6 if v.d > u.d+w(u,v)
7 return FALSE
8 return TRUE
每一次处理对应的是 算法第 2～4 行 for 循环的一次循环，该循环对图的 每条边 进行一次松弛操作。在进行了 |V| - 1 次松弛操作后，算法第 5～8 行负责 检查图中是否存在权重为负值的环路 并返回与之相适应的布尔值
Bellman-Ford 算法的总运行时间为 O(VE)
2、要证明 Bellman-Ford 算法的正确性，首先证明 在没有权重为负值的环路的情况下，该算法 正确计算出从源结点可以到达的所有结点之间的最短路径权值
引理 24.2 设 G = (V, E) 为一个带权重的源结点为 s 的有向图，其权重函数为 w:E→R。假定图 G 不包含从源结点 s 可以到达的权重为负值的环路。那么在算法 BELLMAN-FORD 的第 2～4 行的 for 循环执行了 |V| -1 次之后，对于所有从源结点 s 可以到达的结点 v，我们有 v.d = δ(s, v)
证明：通过使用路径松弛性质来证明本引理。考虑任意从源结点 s 可以到达的结点 v，设 p = <v0, v1, …, vk> 为从源结点 s 到结点 v 之间的任意一条最短路径，这里 v0=s，vk=v。因为最短路径都是简单路径，p 最多包含 |V| -1 条边，因此 k ≤ |V| -1。算法第 2～4 行的 for 循环 每次松弛所有的 |E| 条边。在第 i 次松弛操作时，这里 i=1, 2，…, k，被松弛的边中包含 (vi-1, vi)（路径上的边 按照顺序逐步被松弛）
在第一次迭代时，路径上的第一条边 (v0, v1) 被松弛，这将更新 v1 的最短路径估计值，使其等于从 s 到 v1 的最短路径权重
在第二次迭代时，路径上的第二条边 (v1, v2) 被松弛，更新 v2 的最短路径估计值为从 s 到 v2 的最短路径权重
依此类推，在第 k 次迭代时，路径上的边 (v_k−1, vk) 被松弛，最终更新 vk 的最短路径估计值 k.d 为 δ(s, vk)，也就是从源点 s 到终点 v 的最短路径权重
根据路径松弛性质，v.d = vk.d = δ(s, vk) = δ(s, v)
3、推论 24.3 设 G = (V, E) 是一带权重的源结点为 s 的有向图，其权重函数为 w: E→R。假定图 G 不包含从源结点 s 可以到达的权重为负值的环路，则对于所有结点 v∈V，存在一条从源结点 s 到结点 v 的路径当且仅当 BELLMAN-FORD 算法终止时 v.d < ∞
4、定理 24.4 (Bellman-Ford 算法的正确性)
设 BELLMAN-FORD 算法运行在一帯权重的源结点为 s 的有向 G = (V, E) 上，该图的权重函数为 w: E→R。如果图 G 不包含从源结点 s 可以到达的权重为负值的环路，则算法将返回 TRUE 值，并且对于所有结点 v∈V，前驱子图 Gπ 是一棵根结点为 s 的最短路径树。如果图 G 包含一条从源结点 s 可以到达的权重为负值的环路，则算法将返回 FALSE 值
证明：
首先证明，对于所有结点 v ∈ V，在算法 BELLMAN-FORD 终止时，有 v.d = δ(s, v)。如果结点 v 是从 s 可以到达的，则引理 24.2 证明了本论断。如果结点 v 不能从 s 到达，则该论断 可以从非路径性质获得。因此，该论断得到证明
综合前驱子图性质 和 本论断 可以推导出 Gπ 是一棵最短路径树。现在，我们使用这个论断来证明 BELLMAN-FORD 算法返回的值 确实判断了 有没有 源点可达的负环路
在算法 BELLMAN-FORD 终止时，对于所有的边 (u, v) ∈ E
因此，它一定返回的是 TRUE 值
现在，假定图 G 包含一个权重为负值的环路，并且该环路可以从源结点 s 到达
使用反证法。假设 Bellman-Ford 算法返回的是 TRUE 值，则 vi.d ≤ v_i-1.d + w(v_i-1, vi)，这里 i=1, 2，…，k。将环路 c 上的所有这种不等式加起来，有
由于 v0=vk，环路 c 上的每个结点在上述求和表达式 ∑vi.d 和 ∑vi-1.d 中刚好各出现一次，因此有
根据推论 24.3，vi.d 对于 i=1, 2，…，k 来取的都是有限值，因此有
与条件
矛盾，因此，得出结论，如果图 G 不包含从源结点 s 可以到达的权重为负值的环路，则 Bellman-Ford 算法返回 TRUE 值，否则返回 FALSE 值
24.1-3 给定 G = (V, E) 是一带权重 且没有权重为负值的环路的有向图，对于所有结点 v∈V，从源结点 s 到结点 v 之间的最短路径中，包含边的最大条数为 m。（这里，判断最短路径的依据是权重，不是边的条数）请对算法 BELLMAN-FORD 进行简单修改，可以让他在 m+1 遍松弛操作之后终止，即使 m 不是一个事先知道的一个数值
提前终止条件：在 Bellman-Ford 算法的每次迭代中，如果在一次完整的松弛过程中，所有的边 (u, v) 都没有引起最短路径估计值
v.d 的变化（即不再有松弛操作能更新任何结点的最短路径），那么可以认为最短路径 已经确定，此时算法可以提前终止，而无需再继续剩余的松弛操作
def Bellman_Ford_early_terminate(G, w, s):
# 初始化距离和前驱
Initialize-Single-Source(G, s)
# 对所有节点最多进行 |V| - 1 次松弛操作
for i from 1 to |V| - 1:
# 标记这次迭代是否有任何更新发生
updated = False
# 对每条边 (u, v) 进行松弛操作
for each edge (u, v) in E[G]:
if Relax(u, v, w):
updated = True # 如果松弛操作更新了距离
# 如果这次松弛操作中没有任何更新，提前终止
if not updated:
break
# 进行负环检测（可选）
for each edge (u, v) in E[G]:
if d[v] > d[u] + w(u, v):
return "Graph contains a negative-weight cycle"
return d, π # 返回最短路径估计值和前驱
24.1-4 修改 Bellman-Ford 算法，使其对于所有结点 v 来说，如果从源结点 s 到结点 v 的一条路径上存在权重为负值的环路，则将 v.d 的值设置为 -∞
只要将 所有 对于在环路中的点（需要标记）来说 可达的点 设为 -∞ 即可
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 u ∈ marked vertices
DFS-MARK(u)
DFS-MARK(u)
if u != NIL and u.d != -∞
u.d = -∞
for each v in G.Adj[u]
DFS-MARK(v)
2、有向无环图中的单源最短路径问题
1、根据结点的 拓扑排序次序（BF算法之所以需要迭代 N-1 次就是因为是没有顺序的乱撞（暴力循环）） 对带权重的有向无环 G=(V, E) 进行边的松弛操作，我们便可以在 θ(V+E) 时间内 计算出从单个源结点到所有结点之间的最短路径。在有向无环图中，即使存在权重为负值的边，但是 因为没有权重为负值的环路，最短路径都是存在的
2、拓扑排序 是一种将所有顶点线性排序的方法，保证对于每一条有向边 u → v，顶点 u 在排序中出现在顶点 v 之前。拓扑排序的常见算法有两种：Kahn 算法（基于入度）和 深度优先搜索（DFS）算法
Kahn 算法的伪代码：
def kahn_topological_sort(graph):
in_degree = {u: 0 for u in graph} # 初始化所有顶点的入度为 0
for u in graph:
for v in graph[u]:
in_degree[v] += 1 # 计算每个顶点的入度
queue = [u for u in in_degree if in_degree[u] == 0] # 找到所有入度为 0 的顶点
topological_order = []
while queue:
u = queue.pop(0) # 从队列中取出一个顶点
topological_order.append(u)
for v in graph[u]:
in_degree[v] -= 1 # 移除顶点 u 的出边，更新顶点 v 的入度
if in_degree[v] == 0:
queue.append(v) # 如果顶点 v 的入度变为 0，将其加入队列
# 如果拓扑排序的结果包含了所有顶点，说明排序成功，否则图中有环
if len(topological_order) == len(in_degree):
return topological_order
else:
return "Graph has a cycle"
时间复杂度：
O(V+E)，其中 V 是顶点数，E 是边数。因为我们需要遍历每个顶点和每条边一次
DFS 算法的伪代码：
def dfs_topological_sort(graph):
visited = set() # 记录访问过的顶点
stack = [] # 栈来存储拓扑排序的结果
def dfs(v):
visited.add(v) # 标记当前顶点已访问
for neighbor in graph[v]:
if neighbor not in visited:
dfs(neighbor)
stack.append(v) # 当 v 的所有邻居都已处理，将 v 压入栈
# 对图中的每个顶点执行 DFS
for v in graph:
if v not in visited:
dfs(v)
return stack[::-1] # 返回栈的逆序即为拓扑排序
时间复杂度：同样为 O(V + E)。每个顶点和每条边都只会被访问一次
3、算法 先对有向无环图进行拓扑排序，以便确定 结点之间的一个线性次序。如果 有向无环图包含从结点 u 到结点 v 的一条路径，则 u 在拓扑排序的次序中 位于结点 v 的前面。只需要按照拓扑排序的次序 对结点进行一遍处理即可（确保后面的点 松弛之前 前面的点已经 松弛完毕）。每次对一个结点进行处理时，对从该结点发出的所有边进行松弛操作
DAG-SHORTEST-PATHS(G,w,s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G,s)
3 for each vertex u, taken in topologically sorted order
4 for each vertex v∈G.Adj[u]
5 RELAX(u,v,w)
算法第 1 行的拓扑排序时间为 Θ(V + E)。第 2 行对 INITIALIZE-SINGLE-SOURCE 的调用所需时间为 Θ(V)。第 3~5 行的 for 循环（外循环）对于每个节点执行一遍，因此，第 4~5 行的 for 循环（内循环）对每条边刚好松弛一次。(注意，我们这里使用了聚合分析。) 因为内循环每次的运行时间为 Θ(1)，算法的总运行时间为 Θ(V + E)。对于以邻接链表法表示的图来说，这个时间是线性级
通过聚合分析，可以分析算法的总体成本，而不是逐步分析每个操作的成本
定理 24.5 如果带权重无环路的有向图 G = (V, E) 有一个源结点 s，则在算法 DAG-SHORTEST-PATHS 终止时，对于所有的结点 v ∈ V，有 v.d = δ(s, v)，且前驱子图 Gπ 是一棵最短路径树
证明：因为算法是 按照拓扑排序的次序 来对结点进行处理，所以对路径 p 上的边的放松次序为 (v0, v1), (v1, v2), …, (vk-1, vk)。根据路径松弛性质，对于 i=0, 1, …, k，在算法终止时有 vi.d = δ(s, vi)。最后，根据 前驱子图性质，Gπ 是一棵最短路径树
4、算法 DAG-SHORTEST-PATHS 的一个有趣的应用是在 PERT 图的分析中 进行关键路径的判断。PERT 图是一个有向无环图，在这种图中，每条边代表需要进行的工作，边上的权重 代表执行该工作所需要的时间
如果边 (u, v) 进入结点 v，边 (v, x) 离开结点 v（从结点 v 发出），则工作 (u, v) 必须在工作 (v, x) 前完成。PERT 图中的一条路径代表的是 一个工作执行序列。关键路径 则是该有向无环图中一条最长的路径，该条路径代表执行任何工作序列所需要的最长时间。因此，关键路径上的权重提供的 执行所有工作所需时间的下界
可以使用 下面两种方法中的任意一种 来找到 PERT 图中的关键路径：
- 将所有权重变为负数，然后运行 DAG-SHORTEST-PATHS
- 运行 DAG-SHORTEST-PATHS，但在初始化时将 ∞ 替换为 -∞ ，在松弛过程中将“ > ”替换为“ <”
24.2-2 假定将 DAG-SHORTEST-PATHS 的第三行改为：
3 for the first |V| - 1 vertices, taken in topologically sorted order
证明：该算法的正确性保持不变
DAG-SHORTEST-PATHS(G,w,s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G,s)
3 for each vertex u, taken in topologically sorted order
4 for each vertex v∈G.Adj[u]
5 RELAX(u,v,w)
当 到达顶点 v（拓扑排序中的最后一个顶点）时，它必须有出度为 0。否则 将会有一条从较晚顶点指向较早顶点的边，这会导致矛盾。因此，第4行的 for 循环主体 从未针对该最终顶点执行，所以 可以不考虑它
24.2-3 上面描述的 PERT 图的公式有一点不太自然。在一个更自然的结构下，图中的结点 代表要执行的工作，边 代表工作之间的次序限制，即边 (u, v) 表示工作 u 必须在工作 v 之前执行。在这种结构的图中，将权重赋给结点，而不是边。请修改 DAG-SHORTEST-PATHS 过程，使得其可以在线性时间内 找出这种有向无环图中一条最长的路径
24.2-4 给出一个有效的算法 来计算一个有向无环图中的路径总数
需要加 1，因为 边本身 也算一条路径，新的路径包括：前面结点的每一条路径 加这条边 + 边本身
3、Dijkstra 算法
1、Dijkstra 算法解决的是 带权重的有向图上 单源最短路径问题，该算法 要求所有边的权重都为非负值。如果所采用的实现方式合适，Dijkstra 算法的运行时间要低于 Bellman-Ford 算法的运行时间
Dijkstra 算法 在运行过程中维护的关键信息是 一组节点集合 S。从源节点 s 到该集合中每个节点之间的最短路径 已经找到。算法 重复从节点集 V - S 中选择最短路径估计最小的节点 u，将 u 加入到集合 S，然后对所有从 u 发出的边进行松弛。使用一个最小优先队列 Q 来保存节点集合，每个节点的关键值为其 d 值
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S = ∅
3 Q = G.V
4 while Q ≠ ∅
5 u = EXTRACT-MIN(Q)
6 S = S ∪ {u}
7 for each vertex v ∈ G.Adj[u]
8 RELAX(u, v, w)
算法所维持的不变式为 Q = V − S，该不变式在算法第 4～8 行的 while 循环过程中保持不变。算法第 3 行对最小优先队列 Q 进行初始化，将所有的结点 V 放在该队列里
结点 u 是集合 V−S 中所有结点的 最小 最短路径估计。然后，在算法的 7～8 行，对所有从结点 u 发出的边 (u, v) 进行松弛操作。如果一条经过结点 u 的路径 能够使得从源结点 s 到结点 v 的最短路径权重 比当前的估计值更小，则 对 v.d 的值和前驱
v.π 的值进行更新
第 3 行之后，再不会 在队列 Q 中插入任何结点，而每个结点从 Q 中被抽取的次数 和 加入集合 S 的次数均为一次，因此，算法第 4～8 行的 while 循环的执行次数刚好为∣V∣ 次
因为 Dijkstra 算法总是选择集合 V - S 中“最轻” 或 “最近”的结点 来加入到集合 S 中，该算法使用的是贪心策略。关键是证明这样一个事实：该算法 在每次选择结点 u 加入到集合 S 时，有 u.d = δ(s, u)
2、定理 24.6 （Dijkstra 算法的正确性） Dijkstra 算法运行为带权重的有向图 G = (V, E) 时，如果所有权重为非负值，则在算法终止时，对于所有结点 u ∈ V，有 u.d = δ(s, u)
证明：使用下面的循环不变式：
在算法第 4～8 行的 while 语句的每次循环开始前，对于每个结点 v ∈ S，有 v.d = δ(s, v)。只需要证明对于每个结点 u ∈ V，当结点 u 被加到集合 S 时，有 u.d = δ(s, u)
初始化：初始时，S = ∅，因此，循环不变式直接成立
保持：希望证明在每次循环中，对于 加入到集合 S 的结点 u 来说，u.d = δ(s, u)
使用反证法 来证明此结论。设结点 u 是第一个在加入到集合 S 时使得该方程式不成立的结点，即 u.d ≠ δ(s, u)。下面将注意力集中在 把结点 u 加入到集合 S 的这遍循环的开始，并通过对从结点 s 到结点 u 的最短路径进行检查来得出结论 u.d = δ(s, u)
（反证设为 不是直达的，有中转的结点）
由于结点 s 是第一个加入到集合 S 中的结点并且 s.d = δ(s, s) = 0，结点 u 必定与结点 s 不同，即 u ≠ s。因为 u ≠ s，在即将把结点 u 加入到集合 S 时，有 S ≠ ∅。此时，一定存在某条从结点 s 到结点 u 的路径，否则，根据非路径性质将有 u.d = δ(s, u) = ∞，而这将违反我们的假设 u.d ≠ δ(s, u)。因为至少存在一条从 s 到 u 的路径，所以也存在一条从 s 到 u 的最短路径 p
在将结点 u 加入到集合 S 之前，路径 p 连接的是集合 S 中的一个结点（即 s）和 V - S 中的一个结点（即 u）。让我们考虑路径 p 上第一个满足 y ∈ V - S 的结点 y，设 x ∈ S 为结点 y 在路径 p 上的前驱，则如图所示，可以将路径 p 分解为 
因为选择的结点 u 是 第一个在加入到集合 S 时不满足条件 u.d ≠ δ(s, u) 的结点，在将结点 x 加入到集合 S 时，有 x.d = δ(s, x)。此时，边 (x, y) 将被松弛，根据收敛性质可以得出 在将结点 u 加入到集合 S 时，y.d = δ(s, y)（收敛性质 (引理 24.14) 对于某些结点 u, v ∈ V，如果 s → u → v 是图 G 中的一条最短路径，并且在对边 (u, v) 进行松弛前的任意时间有 u.d = δ(s, u)，则在之后的所有时间有 v.d = δ(s, v)）
可以通过反证来证明 u.d = δ(s, u)。因为结点 y 是从结点 s 到结点 u 的一条最短路径上位于 u 前面的一个结点，并且所有的边权重均非负，所以有 δ(s, y) ≤ δ(s, u)
在算法第 5 行选择结点 u 时，结点 u 和 y 都在集合 V - S 里，所以有 u.d ≤ y.d（不然 y 就变成 u 了）。因此，式(24.2)中的两个不等式事实上都是等式，即
y.d = δ(s,y) = δ(s,u) = u.d
因此 u.d = δ(s, u)，而这与 所选择的结点 u 矛盾。因此，在结点 u 被加人到集合 S 时有 u.d = δ(s, u)，并且该等式在随后的所有时间内都保持成立
终止：在算法终止时，Q = ∅。该事实与之前的不变式 Q = V - S 一起说明了 S = V。因此，对于所有的结点 u ∈ V，有 u.d = δ(s, u)
3、推论 24.7 如果在带权重的有向图 G = (V, E) 上运行 Dijkstra 算法，其中的权重皆为非负值，源结点为 s，则在算法终止时，前驱子图 Gπ 是一棵根结点为 s 的最短路径树
4、分析
该算法 执行三种优先队列操作 来维持最小优先队列：INSERT（算法第 3 行所隐含的操作）、EXTRACT-MIN（算法第 5 行）和 DECREASE-KEY（隐含在算法第 8 行所用的 RELAX 操作中）。该算法 对每个节点调用一次 INSERT 和 EXTRACT-MIN 操作
因为每个节点仅被加入到集合 S 一次
邻接链表 Adj[u] 中的每条边在整个算法运行期间 也只被检查一次（算法第 7~8 行的 for 循环里）。由于所有邻接链表中的边的总数为 |E|，该 for 循环的执行次数一共为 |E| 次，因此该算法调用 DECREASE-KEY 最多 |E| 次
Dijkstra 算法的总运行时间 依赖于 最小优先队列的实现。首先考虑第一种情况：通过利用节点的编号为 1~|V| 来维持最小优先队列。在这种情况下，将 v.d 的值存放在数组的第 v 个记录里。每次 INSERT 和 DECREASE-KEY 操作的执行时间为 O(1)，每次 EXTRACT-MIN 的操作时间为 O(V)（因为需要搜索整个数组），算法的总运行时间为 O(V2 + E) = O(V2)
如果 讨论的是稀疏图，特别地，如果 E = o(V2/ lgV)，则可以 使用二叉堆 来实现最小优先队列，从而改善算法的运行时间。每次 EXTRACT-MIN 操作的执行时间为 O(lgV)。和前面一样，一共有 |V| 次这样的操作。构建最小二叉堆的成本为 O(V)。每次 DECREASE-KEY 操作的执行时间为 O(lgV)，而最多有 |E| 次这样的操作。因此，若所有节点 都可以从源节点到达，算法的总运行时间为 O((V+E) lgV)，即 O(E lgV)。若 E = o(V2 / lgV)，则该时间成本相对于直接实现的 O(V2) 成本有所改善（在 E = o(V2 / lgV) 时，O(E lgV) 小于 O(V2)）
可以将 Dijkstra 算法的运行时间 改进到 O(VlgV + E)，方法是使用斐波那契堆 来实现最小优先队列。在这种实现下，每次 EXTRACT-MIN 的摊还代价为 O(lgV)，每次 DECREASE-KEY 的摊还代价 改进为 O(1)。斐波那契堆 提出的动机 就是因为人们观察到 Dijkstra 算法调用的 DECREASE-KEY 操作通常比 EXTRACT-MIN 操作更多，因此，任何能够将 DECREASE-KEY 操作的摊还代价降低到 o(lgV) 而又不增加 EXTRACT-MIN 操作的摊还代价的方法 都将产生比二叉堆的渐近性能更优的实现
5、Dijkstra 算法 既类似于广度优先搜素，也有点类似于计算最小生成树的 Prim 算法
它与广度优先搜索的相似点 在于集合 S 对应的是广度优先搜索中的黑色结点集合：正如集合 S 中的结点的最短路径权重 已经计算出来一样，在广度优先搜索中，黑色结点的正确的广度优先距离 也已经计算出来
Dijkstra 算法像 Prim 算法的地方是，两个算法 都使用最小优先队列来寻找给定集合（Dijkstra 算法中的 S 集合 与 Prim 算法中逐步增长的树）之外的 “最轻” 结点，将该结点加入到集合里，并对位于 集合外面的结点的权重进行相应调整
24.3-2 举出一个包含负权重的有向图，使得 Dijkstra 算法在其上运行时将产生不正确的结果
定理 24.6 的证明也不再适用，因为 无法保证
δ(s, y) ≤ δ(s, u)
24.3-4 Gaedel 教授编写了一个程序，他声称 该程序实现了 Dijkstra 算法。对于每个结点 v∈V，他的程序在任何时候都有 d[v] ≤ δ(s, v)。然而，他发现这个程序从未更新过 π[v]。Gaedel 教授的程序正确吗
24.3-5 Newman 教授觉得自己的发现了 Dijkstra 算法的一个更简单的证明。他声称 Dijkstra 算法对最短路径上的每条边的松弛次序 与该条边在这条最短路径中的次序相同，因此，路径松弛性质 适用于 从源结点可以到达的所有结点。请构造一个有向图来说明 Dijkstra 算法并不一定按照最短路径中边出现的次序来对边进行松弛，从而证明教授是错的
Newman 教授的论断是错误的。Dijkstra 算法不一定按照 最短路径上边的顺序 进行松弛，松弛的顺序 取决于 优先队列中顶点的选择顺序，Dijkstra 算法 会优先处理当前最小距离的顶点，但这并不保证 在同一条路径上的所有边会按顺序松弛
24.3-6 给定有向图 G = (V, E)，每条边 (u, v) ∈ E 有一个关联值 r(u, v)，该关联值是一个实数，其范围为 0 ≤ r(u, v) ≤ 1，其代表的意思是从结点 u 到结点 v 之间的通信链路不失效的概率，并且假定这些概率之间相互独立。请给出一个有效的算法 来找到任意两个结点之间最可靠的通信链路
24.3-8 给定带权重的有向图 G = (V, E)，其权重函数为 w: E→{0,1,2,…,W}，这里 W 为某个非负整数。请修改 Dijkstra 算法来计算 从给定源结点 s 到所有结点之间的最短路径。该算法时间应为 O(WV + E)
24.3-10 假设 给定带权重的有向图 G = (V, E)，从源结点 s 发出的边的权重可以为负值，而其他所有边的权重 全部是非负值，同时，图中不含权重为负值的环路。证明：Dijkstra 算法可以正确计算出 从源结点 s 到所有其他结点之间的最短路径
后续步骤中，所有边的权重均为非负，已确定的最短路径不会被再次更新
4、差分约束和最短路径
讨论线性规划中 的一个特例，该特例 可以 被归约为单源最短路径问题。这样，可以通过运行 Bellman-Ford 算法来解决单源最短路径问题，从而解决 这种特殊的线性规划问题
1、线性规划
可以 将某个给定问题 看做是一个多项式规模的线性规划问题，则可以 立即获得一个多项式时间的算法解。其次，对于线性规划的许多特殊情况，存在着更快的算法。例如，单源单目的地最短路径问题
并不关注目标函数，而仅仅是希望找到一个可行解
2、差分约束系统
在一个差分约束系统中，线性规划矩阵 A 的每一行包括一个 1 和一个 −1，其他所有项皆为 0。因此，由 Ax ≤ b 所给出的约束条件变为 m 个涉及 n 个变量的差额限制条件，其中的每个约束条件是 如下所示的简单线性不等式：
一个可能答案是 x = (−5, −3, 0, −1, −4)，这个问题的答案有多个。另一个答案是 x = (0, 2, 5, 4, 1)。这两个答案之间存在着关联关系：向量 x′ 中每个元素比向量 x 中的对应元素的取值大 5
引理 24.8
设向量 x = (x1, x2, …, xn) 为差分约束系统 Ax ≤ b 的一个解，设 d 为任意数，则 x + d = (x1 + d, x2 + d, …, xn + d) 也是该差分约束系统的一个解
证明 对于每个 xi 和 xj，我们有 
差分约束系统 在许多不同的应用里都会出现。例如，未知变量 xi 可能代表的是事件发生的时间。每个约束条件给出的是 在两个事件之间必须间隔的最短时间 或 最长时间
3、约束图
将 m × n 的线性规划矩阵 A 看做成一张由 n 个结点和 m 条边构成的图的邻接矩阵的转置
图中的每个结点 vi 对应 n 个未知变量 xi 中的一个。图中的每条有向边 则对应 m 个不等式中的一个
给定差分约束系统 Ax ≤ b，其对应的约束图是 一个带权重的有向图 G = (V, E)，这里：
约束图 包含一个额外的结点 v0，用来保证 图中至少存在一个结点，从其出发可以到达所有的其他结点。因此，结点集合 V 由代表每个变量 xi 的结点 vi 和额外的结点 v0 所组成。边集合 E 包含的是代表每个差分约束的边，再加上边 (v0, vi)，i = 1，2，…，n。如果 xi – xj ≤ bk 是一个差分约束条件，则边 (vi, vj) 的权重为 w(vi, vj) = bk。所有从结点 v0 发出的边的权重为 0
下面的定理 将证明可以通过 在对应的约束图中 寻找最短路径权重 来找到一个差分约束系统的一个解
定理 24.9 给定差分约束系统 Ax ≤ b，设 G = (V, E) 是该差分约束系统所对应的约束图。如果图 G 不包含权重为负值的环路，则
是该系统的一个可行解。如果图 G 包含权重为负值的环路，则该系统没有可行解
证明：根据三角不等式，δ(v0, vj) ≤ δ(v0, vi) + w(vi, vj)，即 δ(v0, vj) − δ(v0, vi) ≤ w(vi, vj)。因此，如果令 xi = δ(v0, vi) 和 xj = δ(v 0 ,vj)，则 xi 和 xj 满足对应边 (vi, vj) 的差分约束条件 xj − xi ≤ w(vi, vj)
如果约束图包含权重为负值的环路，则差分约束系统没有可行解。不失一般性，设权重为负值的环路为 
假设向量 x 有一个满足上述 k 个不等式的解，则这个解 必须同时满足将 k 个不等式加起来之后 形成的新不等式（只剩一头一尾）。如果将不等式的左边 进行求和，每个未知变量 xi 被加进来一次，被减去一次 (vi = vk 意味着 x1 = xk，因为是环)，使得左边的和为 0。不等式右边的和为 wc，因此有 0 ≤ wc。但是 c 是一个权重为负值的环路，因此 w© < 0，这样我们得出矛盾：0 ≤ w(c) < 0
4、求解差分约束系统
可以使用 Bellman-Ford 算法 来求解差分约束系统。因为约束图 包含从源点 v0 到所有其他结点的边，任何权重为负值的环路 都可以从结点 v0 到达。如果 Bellman-Ford 算法返回 TRUE 值，则最短路径权重给出的是 该系统的一个可行解。如果 Bellman-Ford 算法返回 FALSE 值，则差分约束系统 没有可行解
一个有 n 个未知变量和 m 个约束条件的差分约束系统 所生成的约束图有 n+1 个结点 和 n+m 条边。因此，使用 Bellman-Ford 算法，可以在 O((n+1) (n+m)) = O(n2 + nm) 时间内 求解该系统
