c++ - 如果所有路径都具有相同的长度，如何开始 Edmonds-Karp 实施？

Question

如果所有路径的长度相同，如何选择Edmonds-Karp 算法的起始路径？在这种情况下，最大流量根据路径顺序决策而变化。

Answer 1

我认为如何处理顶点容量存在问题。这样做的通常方法是将顶点 v 分成两个顶点 v' 和 v'' 并在 v' 和 v'' 之间添加一条具有顶点容量的边。所有连接到 v 的边（即 v 是目的地）都应该与新图中的 v' 连接，并且来自 v 的所有边都应该从新图中的 v'' 开始。

您可能知道，当您让 xaby 3 流动时，您会增加反向边缘的容量。在这种情况下，您将添加边 ax 3、ba 3、yb 3。如果您按照我描述的方式进行图形表示，您将看到在第一种情况下可以使用额外的流程（我认为它可以通过 xadcby，但尚未检查）。

最短路径的选择不应该改变答案——正如我在评论中提到的，我们只在每个步骤中选择最短路径以避免性能受损的不良情况，但答案总是相同的。

希望这个答案有帮助。