Dijkstra 算法的修改，用于处理负权重及其时间复杂度

Question

到处都写着 Dijkstra 算法不适用于负权值的图。但为什么我们不能稍微修改一下呢？假设我们有一个存储每个节点成本的哈希图，我们还有一个包含所有已处理节点的哈希图。如果我们找到到已处理节点的更短路径，则将其从已处理节点列表中删除并将其添加到堆中。在我看来，这样修改后的算法的时间复杂度只会相差一个常数，如果我错了，请解释。如果没有差异，那么为什么说迪杰斯特拉算法不适用于负权重？

附注我在写这个问题时使用了翻译，对于文本中的错误（如果有的话）我深表歉意

Answer 1

在我看来，这种修改算法的时间复杂度只会相差一个常数，如果我错了请解释

它的差异可以大于一个常数。这是一类图，我们得到的时间复杂度更差：

此类图有 2𝑛−1 个节点，编号从 -𝑛+1 到 𝑛−1。当我们首先“向下”（到节点 -1、-2、-3...）然后返回到节点 1 时，从节点 0 到节点 1 的路径的成本会降低。

如果我们在节点 0 处执行 Dijkstra 算法，则第一个扩展的节点将是节点 1 到 𝑛−1，到达最右边节点的成本为 𝑛−1。

然后节点 -1 将被扩展，因此相同的节点 1 到 𝑛−1 将再次放入优先级队列中......从而减少 𝑛−2 到达最右边节点的成本。

如此继续：节点-2将参与，然后节点-3，...直到底部的节点参与。每次节点 1 到 𝑛−1 都必须放回队列中。

因此，对于图的这个子集（具有不同的𝑛），时间复杂度为 O(𝑛²) = O(|𝑉|²)，这比 Dijkstra 算法对没有负权重的图所确保的时间复杂度更差，即 O(|𝐸| + |𝑉|日志|𝑉|)