dijkstra最短路径手算

Dijkstra算法是一种用于寻找带权重的图中两点之间最短路径的算法。下面是手算Dijkstra最短路径的步骤：

1. 创建一个距离表，用于记录起始节点到其他节点的距离。将起始节点距离设为0，其他节点距离设为无穷大。
2. 创建一个集合S，用于存储已经找到最短路径的节点。
3. 选择距离表中距离最小且不在集合S中的节点，将其加入集合S。
4. 更新距离表中未加入集合S的节点的距离。对于已加入集合S的节点，遍历其相邻节点，将其距离更新为当前节点到起始节点的距离加上当前节点到相邻节点的距离，如果更新的距离小于距离表中的距离，则更新距离表中的距离。
5. 重复步骤3和步骤4，直到所有节点都加入集合S。
6. 根据距离表找到最短路径。

以下是一个简单的示例来说明Dijkstra算法的手算过程：

假设我们有以下图形：

     A
   /   \
  1     2
 /       \
B---3---C
  \       /
   4     5
    \   /
     D

起始节点为A，我们需要找到A到其他节点的最短路径。

1. 初始化距离表：A: 0, B: ∞, C: ∞, D: ∞
2. 选择距离最小且不在集合S中的节点，将其加入集合S。此时选择A，加入集合S。
距离表变为：A: 0, B: ∞, C: ∞, D: ∞
3. 更新距离表：遍历A的相邻节点B和C。
B: 1 (A到B的距离为1)
C: 2 (A到C的距离为2)
距离表变为：A: 0, B: 1, C: 2, D: ∞
4. 选择距离最小且不在集合S中的节点，将其加入集合S。此时选择B，加入集合S。
距离表变为：A: 0, B: 1, C: 2, D: ∞
5. 更新距离表：遍历B的相邻节点A和D。
A: 0 (距离表中的距离小于当前计算出的距离，无需更新)
D: 5 (B到D的距离为5)
距离表变为：A: 0, B: 1, C: 2, D: 5
6. 选择距离最小且不在集合S中的节点，将其加入集合S。此时选择C，加入集合S。
距离表变为：A: 0, B: 1, C: 2, D: 5
7. 更新距离表：遍历C的相邻节点A和D。
A: 0 (距离表中的距离小于当前计算出的距离，无需更新)
D: 5 (距离表中的距离小于当前计算出的距离，无需更新)
距离表变为：A: 0, B: 1, C: 2, D: 5
8. 选择距离最小且不在集合S中的节点，将其加入集合S。此时选择D，加入集合S。
距离表变为：A: 0, B: 1, C: 2, D: 5
9. 更新距离表：遍历D的相邻节点B。
B: 1 (距离表中的距离小于当前计算出的距离，无需更新)
距离表变为：A: 0, B: 1, C: 2, D: 5
10. 所有节点都已加入集合S，找到最短路径。
A到B的最短路径为A -> B，距离为1。
A到C的最短路径为A -> C，距离为2。
A到D的最短路径为A -> B -> D，距离为5。

希望这个简单的示例能够帮助你手算Dijkstra最短路径。