Dijkstra 松弛:暂定距离如何变成确定距离?
逐步观察“选最小未确定节点”和“检查一条出边”两个动作;再用负权反例检验前提。
一个距离,为什么能被永久确定?
找暂定距离最小的未确定节点;颜色表示不同状态。
当前选中 已确定 金色边 = 当前松弛
从 A 出发的距离
当前步骤
进度—
动作—
当前节点—
检查边—
已确定集合—
d[v] = min(d[v], d[u] + w)
点击“下一步”,先确定当前最小暂定距离。
结论与可信度检查
边界:Dijkstra 的“确定后不再被推翻”依赖所有可达边权非负;本演示不处理负环,也不代替完整 Bellman–Ford 讲解。