我正在阅读Skiena的算法设计手册，并对网络流问题以及如何评估它感到非常困惑 . 首先，我甚至无法弄清问题究竟是什么解决了 . 我假设你正在尝试使用所有可用的节点/边缘从源发送一个流到接收器，并且你想要最大化这样做的效率，但如果我错了请纠正我 .
本手册首先解释的是剩余流量图 . 对于每个边（i，j），剩余流图最多可以有两条边：
-
具有重量容量（i，j）的边（i，j） - 如果容量 - 流> 0则流（i，j）
-
如果流量> 0，则具有重量流量（i，j）的边缘（j，i）
我怎么知道源头的初始“流量”是什么？不应该有某种起点，一定数量的“数据”（或其他）试图从源头到汇点，以便让我知道通过它的初始流量？也许我误解了甚至代表什么样的流程 .
接下来是关于“增强路径”的讨论 . 对于我的生活，我似乎无法在谷歌搜索有意义的解释 . 增强路径（如果我理解正确的话）是仅使用从源到接收器具有正容量的边的路径 . 根据这本书，“当且仅当它不包含增加路径时，通过网络的流是最佳的” . 怎么可能？我不明白如何在不使用具有正容量的边缘的情况下从源到水槽 . 再说一遍，我可能误会了 .
我困惑的最后一件事与教科书中的图片有关：
我很困惑为什么从S到T不再存在路径，至少在有向残差图中是这样 . 没有箭头进入T，所以这不会显示从T到S的最大流量吗？当没有从S到T的路径时，我不知道这是如何表示从S到T的任何流动 . 有人请清除这个:(