使用基于堆的优先级队列的 Dijkstra 算法的执行时间

Question

我不明白为什么使用基于堆的优先级队列时执行顺序是O(m log n)而不是O(nm log n)。

同时必须处理 n 个节点并评估所有 m 个图的边，在最坏的情况下，算法必须对每条边放松 d(v) （或 v.distance），每条边需要 O(log n) ，所以它会为 O(nm log n)

PD：抱歉我的英语不好。

Answer 1

你说得对，while 循环会访问每个节点和每个边，每个堆操作需要时间 O(log n)，但这并不意味着完成的总工作是 O(mn log n)。

具体来说，循环的每次迭代都集中在某个节点 v 上。当处理节点 v 时，我们访问 v 中的每个传出边，对每个边执行 O(log n) 工作。如果我们对图 v₁、v₂、...、v_n 的节点进行编号，并将节点 v_i 的度数（它接触的边数）表示为 deg(v_i ），这意味着在循环的所有迭代中，我们所做的工作是

O(log n) · (deg(v₁) + deg(v₂) + ... + deg(v_n))。

握手引理表示内部总和等于 2m，因为每条边都被计算两次。这意味着完成的总工作量为 2m · O(log n) = O(m log n)。