Dijkstra 和负权重 - 计算错误的距离重要吗？
Dijkstra and negative weights - does the miscalculated distance matter?
我正在阅读关于为什么 Dijkstra 算法不适用于负权重图的反例，并且为反例给出的图是：
但是，当您 运行 在此图上的算法时，您会得到以下结果，因此对于 A->D，我们错误计算了实际的最短距离（我们得出的结论是 4，而实际上它是 2)，但是指向它的节点似乎毕竟是正确的，所以我们关心什么？
我们从选择边 {A,B} 开始，然后是 {B,D} 所以 {A,D} 距离 = 4 此时 D 的 parent 是 B。之后我们'队列中只剩下 'C'，因此我们选择权重 = 5 的 {A,C} 并更新如下，C 的 parent 为 A，{C,B} 也有权重 -4，因此 B 与 A 的距离变为 1，C 将 A 替换为 B 的 parent。因此，如果我们想要通向 D 的实际顶点，我们会得到 A->C->B->D（正确），只是 D 的距离是错误的，但是我们是否真的得到正确的顶点有关系吗？
其实这个说法是错误的
C has A as its parent, also {C,B} has weight -4, therefore B's distance from A becomes 1 and C replaces A as B's parent.
算法首先找到与源点距离最小的未访问顶点并访问它。现在它将更新（如果可能）所选节点附近所有未访问节点的距离。重复这些步骤，直到访问所有节点。
由于 B 已经被访问过，它的父级不会得到更新。如果您更新 B 的父级，则这不是 Dikjstra 算法。
我正在阅读关于为什么 Dijkstra 算法不适用于负权重图的反例，并且为反例给出的图是：
但是，当您 运行 在此图上的算法时，您会得到以下结果，因此对于 A->D，我们错误计算了实际的最短距离（我们得出的结论是 4，而实际上它是 2)，但是指向它的节点似乎毕竟是正确的，所以我们关心什么？
我们从选择边 {A,B} 开始，然后是 {B,D} 所以 {A,D} 距离 = 4 此时 D 的 parent 是 B。之后我们'队列中只剩下 'C'，因此我们选择权重 = 5 的 {A,C} 并更新如下，C 的 parent 为 A，{C,B} 也有权重 -4，因此 B 与 A 的距离变为 1，C 将 A 替换为 B 的 parent。因此，如果我们想要通向 D 的实际顶点，我们会得到 A->C->B->D（正确），只是 D 的距离是错误的，但是我们是否真的得到正确的顶点有关系吗？
其实这个说法是错误的
C has A as its parent, also {C,B} has weight -4, therefore B's distance from A becomes 1 and C replaces A as B's parent.
算法首先找到与源点距离最小的未访问顶点并访问它。现在它将更新（如果可能）所选节点附近所有未访问节点的距离。重复这些步骤，直到访问所有节点。
由于 B 已经被访问过，它的父级不会得到更新。如果您更新 B 的父级，则这不是 Dikjstra 算法。