缩减费用
原始-对偶算法的关键，是把原费用重标定为缩减费用。这样做的目标是让残量网络中的可行边权保持非负。
\[
c_{ij}^{\pi} = c_{ij} - \pi_i + \pi_j
\]
若当前残量边满足 \(c_{ij}^{\pi} \ge 0\)，就可以直接在缩减费用上运行 Dijkstra。
这个网页现在不仅能逐步演示固定案例，还支持 自定义节点、边参数、源点、汇点与目标流量 ，方便你把它直接用作课堂讲解、作业演示或算法实验台。
原始-对偶算法的关键，是把原费用重标定为缩减费用。这样做的目标是让残量网络中的可行边权保持非负。
若当前残量边满足 \(c_{ij}^{\pi} \ge 0\)，就可以直接在缩减费用上运行 Dijkstra。
设本轮在缩减费用图上的最短路距离为 \(d(v)\)，则采用下面的更新规则：
在这个符号约定下，更新后新的缩减费用仍保持非负，而且最短路上的“紧边”会变成 0 缩减费用边。
直观地说，最优状态下，“真正承载流量的有效边”会和对偶势函数对齐。
这正是“原始可行 + 对偶可行 + 紧边增广”能逼近最优解的核心逻辑。
你可以直接编辑节点集合、边集合、源点、汇点和目标流量。应用后，图、目标描述与算法状态会同步刷新。
s,a,b,t。起点,终点,容量,单位费用。边标签格式：容量 / 单位费用 / 当前流量 / 当前正向剩余容量。寻找最短路时，路径会被高亮显示。