我的理解关于Dijkstra算法是正确的吗？

Question

考虑下面的加权有向图：

让我们将节点1视为起始节点，根据Dijkstra算法，我们有以下步骤：

1. 标记节点1为已访问。

2. 到达节点2的最短路径权重为1。标记节点2为已访问。

3. 到达节点3的最短路径权重为30。标记节点3为已访问。 之后，根据算法，节点3的最小路径权重为30，不能更改。 但是，显然，到达节点3的最短路径是4。

请您指出我对算法解释中的任何错误？

- voipp

---

它在第二步就开始出错了。请再仔细看一下算法的描述。 - Henry

Answer 1

简短回答，不，你的理解是错误的。

以下是正确的算法：

Dijkstra算法选择未访问的距离最短的顶点，计算通过该顶点到每个未访问邻居的距离，并在距离更小时更新邻居的距离。完成邻居后将其标记为已访问（设置为红色）。

来源：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 你的错误在于我们选择了具有最低成本的未访问的顶点。

- Andriy Berestovskyy

Answer 2

下表列出了算法的所有步骤。第一列显示被访问的节点，第二列显示已经被探索（但尚未访问）的节点以及当前访问节点的邻居节点。所有节点都表示为三元组（n，d，p），其中n是节点名称，d是从起始节点到该节点的距离，p是前驱节点。正如其他答案和评论所提到的，您将始终访问具有最小距离的探索节点：

visited node | explored nodes
-------------+-------------------------
(1, 0, -)    | (2, 1, 1) (3, 30, 1)
(2, 1, 1)    | (3, 30, 1) (4, 2, 2)
(4, 2, 2)    | (3, 30, 1) (5, 3, 4)
(5, 3, 4)    | (3, 4, 5)     //distance of node 3 is updated
(3, 4, 5)    | 

因此，到节点3的路径实际上经过了所有其他节点，就像预期的那样。

- Nico Schertler