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

图算法

｜

145

图算法

6.5 针对稠密图的 Dijkstra 算法

Dijkstra

算法

还有一个版本适用于稠密图，它使用的是图的邻接矩阵表示。例

6-4

中给

出的

C++

实现不再需要优先队列，它被优化成使用二维数组来包含邻接矩阵。这个版本

的效率是由如何快速在

V

－

S

中得到最小的

dist[]

决定。

while

循环会执行

V

次，因

为

S

每次只会增加一个顶点。在

V

－

S

中找到最小的

dist[u]

需

要检查所有

V

个顶点。

注意，在

while

循环的内循环中，每条边都会被刚好检测一次。由于

E

永远不会大于

V

2

，因此总的运行时间为

O

(

V

2

)

。

针对稠密图的 Dijkstra 算法小结

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

O

(

V

2

+

E

)

singleSourceShortest (G, s)

foreach v in V do

dist[v] =

∞

❶

pred[v] = -1

visited[v] = false

dist[s] = 0

while some unvisited vertex v has dist[v] <

∞

do

❷

u = find dist[u] that is smallest of unvisited vertices

❸

if dist[u] =

∞

then return

visited[u] = true

foreach neighbor v of u do

w = weight of edge (u, v)

newLen = dist[u] + w