algorithm - 我是否使用 Dijkstra 的算法图以正确的方式思考这个负权重？

Question

我一直在努力思考为什么 Dijkstra 算法不适用于负加权图，并且我理解所有示例都有一个进一步的节点指向一个已被充分探索的节点。但是这个例子让我印象深刻；

我这样想对吗？首先探索 A。 A->B 将为 1，A->C 将为 100。然后探索 B 并将 B->D 设置为 2。然后 D 被探索，因为目前它有最短的路径返回源(即在优先级队列的顶部)？

如果 B->D 是 100，那么我会先探索 C(因为 >A->D 是 101)?

人们在每个解释中都没有真正提到的一件事是已经探索/访问了一个节点，它不能再更新，因为 Dijkstra 在优先队列上工作。我只是发现很难理解为什么在这种情况下 C 之前访问了 D。

Answer 1

很简单:当探索/访问/关闭使用 Djikstra 算法的节点时，这意味着您已找到到该节点的最短路径，因此该节点不需要重新探索或重新访问，您已经知道到该节点的最短路径。

例如，当您选择 D 进行探索时，PQ 中有两条路径:

• 成本为 2 的 A-B-D
• 成本为 100 的 A-C

然后选择成本最低的路径。然后，很明显，如果弧成本始终为正，则无法找到通过 A-C 到达 D 的最短路径。已经找到到 D 的最短路径并且该节点已关闭。

然而，当允许负电弧成本时，所有这些推理都不正确，所以这就是为什么 Djikstra 的算法对他们不起作用。