algorithm - Dijkstra算法如何找到最短路径？

Question

当E和B之间没有路径时，最短路径怎么可能是A、C、E、B、D？

Answer 1

Dijkstra 算法按照与广度优先搜索 (BFS) 相同的顺序将节点添加到队列中:当测试节点时，其直接邻居将添加到队列中。
不同之处在于节点从队列中拉出的方式。 BFS 按 FIFO(先进先出)顺序执行此操作，而 Dijkstra 算法则按优先级执行此操作。
具有最高优先级的节点被从队列中拉出。优先级由从原点到该节点的成本设置。
当测试源 A 时，它的直接邻居被添加到队列中，因此队列包含 2 个节点:

B(10), C(3)

为了方便起见，我将成本添加到每个节点的名称中。
下一个要从队列中拉出并进行测试的节点是具有最高优先级 = 最低成本的节点，即 C。测试 C 后，队列如下所示:

B(7), E(5), D(11)

B 的成本从 10 更新为 7，因为找到了成本较低的路径(A->C->B)。
下一个要从队列中拉出的节点是 E。测试 E 不会将其任何邻居 (C,D) 添加到队列中。 C已测试完毕，D正在等待测试中。
拉出E后的队列如下所示:

B(7), D(11)

具有最高优先级(起始成本最低)的 B 被从队列中拉出。
测试 B 将 D 的成本更新为 7+2 = 9。现在队列中只有 D:

D(9)

D 被拉出，因为它是目标，所以搜索停止。已找到成本为 9 的正确最短路径。