Dijkstra 松弛:暂定距离如何变成确定距离?

逐步观察“选最小未确定节点”和“检查一条出边”两个动作;再用负权反例检验前提。

先预测,再操作,最后解释

一个距离,为什么能被永久确定?

找暂定距离最小的未确定节点;颜色表示不同状态。

当前选中 已确定 金色边 = 当前松弛

从 A 出发的距离

当前步骤

进度—
动作—
当前节点—
检查边—
已确定集合—
d[v] = min(d[v], d[u] + w)

点击“下一步”,先确定当前最小暂定距离。

结论与可信度检查

边界:Dijkstra 的“确定后不再被推翻”依赖所有可达边权非负;本演示不处理负环,也不代替完整 Bellman–Ford 讲解。

等待完成