📡 Bellman-Ford · 按轮次演示

▶ 📖 问题描述 & 算法原理

Bellman-Ford 算法:求解单源最短路径,允许边权为负(但无负环)。

输入: 顶点数 n,边列表 (u,v,w),源点 s。
输出: 最短距离数组 dist[]。

📌 算法原理

松弛操作: 对每条边 (u,v),若 dist[v] > dist[u] + w,则更新 dist[v] = dist[u] + w。

迭代轮次: 共执行 n-1 轮,每轮遍历所有边进行松弛。

负环检测: 再执行一轮,若仍能松弛则存在负环。

⚠️ 每轮是同时松弛所有边吗?
在实际实现中,一轮中边的松弛顺序会影响中间结果,但最终效果等价于“使用上一轮的距离进行松弛”,因此我们的演示以轮次为单位展示,每轮结束后距离数组统一更新。

📊 图 & 当前距离

📝 当前步骤 0 / 0
点击「下一步」开始演示

📊 距离历史 (每轮结束后)

⬜ 未变  |  🟦 已计算  |  🔵 当前轮  |  🟡 本轮更新  |  ✅ 最终
🎉 最短路径已求出! —