Dijkstra算法中顶点内数值含义咨询及s-z往返最短路径求解疑问

顶点内数值的含义 #

图中顶点内的数值是Dijkstra算法初始化阶段的最短路径距离估计值：

• 起点s到自身的距离设为0
• 起点s到其他所有顶点的初始距离设为无穷大（∞），这些值会在算法执行过程中逐步更新为实际的最短路径长度。

用Dijkstra算法求解s到z的最短路径 #

算法执行步骤 #

1. 初始化：
   • 距离数组dist：dist[s]=0，dist[a]=dist[b]=dist[c]=dist[d]=dist[z]=∞
   • 已访问集合S为空，优先队列（小顶堆）加入(s, 0)
2. 处理顶点s：
   • 更新邻接顶点距离：dist[a] = min(∞, 0+4)=4，dist[b] = min(∞,0+2)=2，将(a,4)、(b,2)加入队列
3. 处理顶点b（当前最小距离为2）：
   • 更新dist[a] = min(4,2+1)=3，dist[c] = min(∞,2+5)=7，将(a,3)、(c,7)加入队列
4. 处理顶点a（当前最小距离为3）：
   • 更新dist[c] = min(7,3+1)=4，dist[d] = min(∞,3+7)=10，将(c,4)、(d,10)加入队列
5. 处理顶点c（当前最小距离为4）：
   • 更新dist[d] = min(10,4+1)=5，dist[z] = min(∞,4+7)=11，将(d,5)、(z,11)加入队列
6. 处理顶点d（当前最小距离为5）：
   • 更新dist[z] = min(11,5+1)=6，将(z,6)加入队列
7. 处理顶点z：
   • 此时dist[z]=6，算法终止

最短路径与长度 #

• 路径：s → b → a → c → d → z
• 总长度：6

用Dijkstra算法求解z返回s的最短路径 #

由于图是无向图（所有边的权重双向相等），最短路径为s到z路径的反向：

• 路径：z → d → c → a → b → s
• 总长度：6
  算法执行逻辑与s到z完全一致，仅需将起点替换为z，逐步更新距离数组即可得到结果。

内容的提问来源于stack exchange，提问作者Seneca