Dijkstra 如何找到这个图中的最短路径？

Question

如果我们必须找到从 0 到 3 的最短路径，我很难理解 Dijkstra 如何在下图中找到最短路径（从我理解它的工作方式）：https://graphonline.ru/tmp/saved/SH/SHBqKyENwJqcCJGM.png

如果算法从0中选择最小的权值并标记0为已访问，它不会选择节点1然后选择节点3吗？它会如何选择节点 2？

Answer 1

根据我的理解，算法会在选择下一个要访问的顶点之前重新计算邻近的、未访问的顶点的暂定距离。当你在1的时候，首先重新计算它的相邻未访问顶点的暂定距离，本例为3。然后选择暂定距离最短的未访问节点，本例为2，访问该节点。

Answer 2

基本上，Dijkstra 只能用于确定给定加权图中从一个源节点到同一图数据结构中的每个其他节点的最短路径，前提是节点可以从源节点到达。 该算法一直运行，直到它访问图中的所有顶点。最短路径不断查找和更新。

也许这个link有助于更好地理解算法本身。 https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e

Answer 3

Dijkstra 算法涉及一个优先级队列，其中保留了从被访问节点可直接到达的所有节点，以及它们到起始节点的距离。

算法将访问节点0，并将节点1和2加入优先队列。然后它将访问节点 1，因为它是优先级队列中最近的节点，并将节点 3 添加到优先级队列中，距离为 6。节点 2 仍在队列中，因为它比节点 3 更靠近节点 0 ，接下来会访问它。当访问到节点2时，会找到到节点3的长度为4的较短路径，因此到节点3的距离将更新为4。然后访问节点3。