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

Question

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

Answer 1

Dijkstra的算法计算出从起始节点（在这种情况下为A）到典型实现中的所有其他节点的最低成本。

为了获得从节点A到其他节点的完整路径，我们遵循向后指针返回答：在此示例中未显示。

S中的节点按照从A开始增加成本的顺序排列。我在主题中包括了一些资源，这可能会有所帮助：

• https://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Melissa.pdf
• https://www.programiz.com/dsa/dijkstra-algorithm

Answer 2

Dijkstra的算法以与广度优先搜索（BFS）相同的顺序将节点添加到队列：在测试节点时，其直接邻居被添加到队列。区别在于从队列pull out节点的方式。 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，这是从A到D的最低成本。]