最小费用最大流问题的 SSP 算法

然而，最大流问题的基本形式并没有考虑流动的成本。一个图的最大流值是一个固定数，可以由多种算法算出来，但具体流法可以有多种，假如每条边单位流量的费用不同，要在所有最大的流中选出费用最小的一个，就成为了
最小费用最大流问题（简称费用流）。在实际应用中，很多网络问题并不仅仅关心流量的最大化，更需要关注流动的费用，例如在交通运输、通信网络、供应链优化等场景中，除了流量外，每条边的费用也会对整体最优解产生重要影响。