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

图算法

｜

141

图算法

里到其他所有机场的最短路径，尽管这个搜索过程可能会在一旦找到前往韦科的路径后

就会终止。

在这个例子中，我们需要最小化的是遍历距离。而在其他应用中，可能会将距离替换为

时间（例如，将数据包在网络上用最快的方式发送），又或者替换为费用（例如，找到

最便宜的从圣约翰斯伯里飞往韦科的方式）。这些问题同样可以归为求解最短路径。

Dijkstra

算法

依赖于一个叫作

优先队列

（

PQ

）的数据结构。

PQ

维护了一个条目集合，

其中每个条目都有一个相关联的整数

优先级

，用于表示每个条目的重要性。

PQ

允许插

入带有关联优先级

p

的条目

x

。

p

的值越低，所代表优先级越高。

PQ

最基础的操作是

getMin

，它返回

PQ

中优先级最低的条目（即最重要的条目）。另外一个

PQ

可能提供的

操作是

decreasePriority

，它会降低

PQ

中某个条目相关联的

优先级

值（即提升其重要性）。

Dijkstra 算法小结

最好情况、平均情况和最坏情况：

O

((

V

+

E

)*log

V

)

singleSourceShortest (G, s)

PQ = empty Priority Queue

foreach v in V do

dist[v] =

∞

❶

pred[v] = -1

dist[s] = 0

foreach v in V do

❷

insert (v, dist[v]) into PQ

while PQ is not empty do

u = getMin(PQ)

❸

foreach ...