algorithm - 执行松弛 m 次的 Dijkstra 算法

Question

在 Dijkstra 算法中，松弛最多 被调用m 次（其中 m = #edges）。我试图找出一些具体的图形示例，确实执行了 m 次放松。我知道每次找到到给定节点的更便宜的路径时都会发生放松，但我无法真正“想象”这种情况。

Answer 1

如评论中所述，一棵树就是一个例子。带循环的示例是具有以下边的 n 个顶点（其中 n 为奇数）的图：

(1, 2) 成本 1

(2, 3) 的成本 1

(1, 3) 成本 10

,

(3, 4) 成本 1

(4, 5) 的成本 1

(3, 5) 成本 10

...

(n - 2, n - 1) 成本 1

(n - 1, n) 成本 1

(n - 2, n) 成本 10

从顶点 1 开始的 Dijkstra 算法总是会首先放松昂贵的 1->3、3->5、5->7、7->9、... (n - 2)->n 边，然后会找到更长的边但更便宜的路径。

给定的图表很好地说明了为什么在 Dijkstra 算法中需要优先级队列。在随机图上，使用简单的队列并在每次边松弛后将顶点推回往往工作得非常快，但在这种情况下，这样的算法将在指数时间内运行。