我是否使用 Dijkstra 的算法图以正确的方式思考这个负权重？
Am I thinking in the right way about this Negative weights using Dijkstra's Algorithm graph?
我一直在努力思考为什么 Dijkstra 的算法不适用于负加权图，并且我理解所有示例都有一个进一步的节点指向一个已被充分探索的节点。但是这个例子让我很吃惊；
我这样想对吗？首先 A 进行了探索。 A->B 将是 1，A->C 将是 100。然后探索 B 并将 B->D 设置为 2。然后 D 被探索，因为目前它有最短的路径回到源头（即在优先级队列的顶部）？
如果 B->D 是 100，我会先探索 C（因为 A->D 是 101），我这样说对吗？ ？
人们在每次解释中都没有真正提到的一件事是节点已经 explored/visited，它不能再更新了，因为 Dijkstra 在优先队列上工作。在这种情况下，我很难理解为什么 D 在 C 之前被访问。
我认为您描述的 Dijkstra 算法仅对正权重函数起作用。特别是 Dijkstra 算法在每个加权（正）图上给出了一个有效的度量 space 结构。另一方面，这似乎不是任意加权图的情况。以具有两个节点 A 和 B 以及它们之间的一条边的权重为 -5 的图为例。在这种情况下，这不会给出 A 和 B 之间的距离。所以你所描述的，我认为会属于某种修改后的 Dijkstra 模型，并且从一个节点到另一个节点的解释不能再被解释为节点之间的距离.
很简单：当使用 Djikstra 算法的节点是 explored/visited/closed 时，这意味着 您已经找到了到该节点的最短路径，因此该节点 不需要重新探索或重新访问，你已经知道到节点的最短路径
例如，当你selectD待探索时，PQ中有两条路径：
- A-B-D 成本为 2
- A-C 费用为 100
成本最低的路径是 selected。然后，很明显，如果弧成本始终为正，则无法找到通过 A-C 到 D 的最短路径。已经找到到 D 的最短路径并且该节点已关闭。
然而，当允许负电弧成本时，所有这些推理都不成立，所以这就是为什么 Djikstra 的算法对他们不起作用。
我一直在努力思考为什么 Dijkstra 的算法不适用于负加权图，并且我理解所有示例都有一个进一步的节点指向一个已被充分探索的节点。但是这个例子让我很吃惊；
我这样想对吗？首先 A 进行了探索。 A->B 将是 1，A->C 将是 100。然后探索 B 并将 B->D 设置为 2。然后 D 被探索，因为目前它有最短的路径回到源头（即在优先级队列的顶部）？
如果 B->D 是 100，我会先探索 C（因为 A->D 是 101），我这样说对吗？ ？
人们在每次解释中都没有真正提到的一件事是节点已经 explored/visited，它不能再更新了，因为 Dijkstra 在优先队列上工作。在这种情况下，我很难理解为什么 D 在 C 之前被访问。
我认为您描述的 Dijkstra 算法仅对正权重函数起作用。特别是 Dijkstra 算法在每个加权（正）图上给出了一个有效的度量 space 结构。另一方面，这似乎不是任意加权图的情况。以具有两个节点 A 和 B 以及它们之间的一条边的权重为 -5 的图为例。在这种情况下，这不会给出 A 和 B 之间的距离。所以你所描述的，我认为会属于某种修改后的 Dijkstra 模型，并且从一个节点到另一个节点的解释不能再被解释为节点之间的距离.
很简单：当使用 Djikstra 算法的节点是 explored/visited/closed 时，这意味着 您已经找到了到该节点的最短路径，因此该节点 不需要重新探索或重新访问，你已经知道到节点的最短路径
例如，当你selectD待探索时，PQ中有两条路径：
- A-B-D 成本为 2
- A-C 费用为 100
成本最低的路径是 selected。然后，很明显，如果弧成本始终为正，则无法找到通过 A-C 到 D 的最短路径。已经找到到 D 的最短路径并且该节点已关闭。
然而，当允许负电弧成本时，所有这些推理都不成立，所以这就是为什么 Djikstra 的算法对他们不起作用。