算法技术手册（原书第2 版）

图算法

｜

143

图算法

图 6-12：Dijkstra 算法扩展集合

S

6.4.1 输入 / 输出

输入是一个有向带权图

G

= (

V

,

E

)

以及一个源顶点

s

∈

V

。图中每一条边

e

= (

u

,

v

)

都有一

个相关联的非负权值。

Dijkstra

算法

生成了两个计算数组。其中主要的计算结果是数组

dist[]

，

它的值表示了

从源顶点

s

到图中每个顶点的距离；次要的计算结果是数组

pred[]

，它用于构造从源顶

点

s

到图中每个顶点的实际最短路径。

边的权值是非负数（即大于等于

0

），如果这个假设不成立，那么

dist[]

的

值有可能包

含无效值。更糟糕的是，如果图中存在一个负值环（即环上的权值之和为负数），那么

Dijkstra

算法

将会陷入死循环。

6.4.2 解决方案

在

Dijkstra

算法

的执行过程中，

dist[v]

代表了从源顶点

s

到

v

的最短路径的最大长度，

且路径只使用

S

集合中的顶点。对于每一个顶点

v

∈

S

，

dist[v]

都是正确的。所幸的是，

Dijkstra

算法

并不需要真正地计算和维护集合

S

。它只需要在最开始创建一个包含

V

中

所有顶点的集合，然后每次从集合中拿出一个顶点，计算出正确的

dist[v]

值。为了方

便起见，我们使用

V

-

S

来指代这个不断缩减的集合。当所有顶点都被访问或者从源顶

点

s

无法访问时，

Dijkstra

算法

结束。

在例

6-3

的

C++

实现中，我们使用了优先队列来存储

V

-

S

中的顶点。在这里优先队

列是

二叉堆

，因为我们可以在常数时间内找到

优先级最小

的顶点（优先级是顶点到

s

的距离）。此外，当

s

到

v

的最短路径找到之后 ...