我对 Dijkstra 算法的理解是否正确？

Question

考虑以下加权有向图：

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

标记为已访问的节点 1。
到节点2的最短路径权重为1。标记节点2已访问。
到节点3的最短路径权重为30。标记节点3已访问。之后，根据算法，节点 3 的最小路径权重为 30，并且无法更改。但是，显然，到 node3 的最短路径是 4.

你能指出我对算法的解释中的任何缺陷吗？

Answer 1

简答是否定的，你的理解不正确。

这是正确的算法：

Dijkstra's algorithm picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

来源：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

你的缺点是我们选择了一个成本最低的未访问顶点。

Answer 2

下面table陈述了算法的所有步骤。第一列显示访问过的节点，第二列显示已经探索过（但尚未访问过）的节点加上当前访问过的节点的邻居。所有节点都表示为三元组(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 的路径实际上按预期遍历了所有其他节点。

我对 Dijkstra 算法的理解是否正确？

Is my understanding of Dijkstra algorithm correct?

algorithm

dijkstra

graph-algorithm