Dijkstra算法总是给出最短路径吗？

Question

我正在学习Dijkstra算法，并有一个基本的问题。我有一个看起来如下的图形...（非负节点）：

A---2-----B------16------D-----3-------F * * * * 3 4 * * C----------2---------------------------E

从上面的图中并不清楚，但AC的距离为3，EF的距离为4。

我想找到A和F之间的最短路径。

考虑目标节点F。当我们考虑它最近的节点时，我们得到D（DF的权重为3，EF为4）。然而，当我们按照该路径行走时，我们得到最短路径为：A，B，D，F（总距离：19）。

一个快速观察告诉我们，最短路径实际上是A，C，E，F（距离：9）。然而，由于在第一步中，E比D更远，所以我们选择了D。

我是否遗漏了什么？Dijkstra算法显然没有展示正确的结果。

- Omi

---

是的，你漏掉了一些东西，该算法总是选择具有最小累积距离的节点作为下一个要探索的节点。我们不会将目标节点标记为已访问，直到它成为最小未访问距离。 - Karuhanga

Answer 1

Dijkstra算法在边的权值均为正数时，总是能够找到最短路径。然而，当图中存在负边权时，该算法可能会失效。

- Brian

---

负边权使得所有非树图上的最短路径算法失效（包括存在负环的情况）。你可以一次又一次地选择负边权，从而得到一个无限短的路径。 - undefined

Answer 2

是的，你确实漏掉了一些步骤。请看下面的第4步。

1. 第一步是将D标记为临时距离3，E标记为临时距离4。 2. 下一步选择D，因为它是未访问过的节点中具有最低临时距离的节点。 3. 然后，您将标记来自D的所有未访问节点及其距离（用临时距离19（3 + 16）标记B）。 4. 接下来选择下一个未访问的具有最低临时距离的节点。这将选择E（4）。 5. 标记所有E的节点及其临时距离。C被标记为6（4+2）。 6. 然后选择下一个未访问的具有最低临时距离的节点。这将选择C（6）。 7. 标记所有C的节点及其临时距离。A被标记为9（6+3）。

当到达距离为9的A时停止。

- The Dark

Answer 3

这个算法在你的图上运行得很好。问题一定是在你的实现中出现了bug。

Visit A
-Set B distance = 0 + 2 = 2, previous = A
-Set C distance = 0 + 3 = 3, previous = A
Visit B
-Set D distance = 2 + 16 = 18, previous = B
Visit C
-Set E distance = 3 + 2 = 5, previous = C
Visit E
-Set F distance = 5 + 4 = 9, previous = E
Visit F
-Set D distance = 9 + 3 = 12, previous = F // you can early-out here if you want
Visit D
-Alternate distance to F: 18 + 3 = 21 (fail since current distance, 9, is smaller)

Shortest path = F.previous = E, E.previous = C, C.previous = A
= A, C, E, F

- MooseBoys

Answer 4

我怀疑你是否真正理解这个算法。看一下这个视频：https://www.youtube.com/watch?v=XB4MIexjvY0

然后从顶点A开始实现它。

Dijkstra算法可以找到任何给定节点到所有其他节点的最短路径，但前提是边权非负。

- Saurabh Patil