如果所有路径都有相同的长度，如何启动Edmonds-Karp实现？

Question

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

Answer 1

我认为在顶点处理容量的方式有一个问题。通常的方法是将顶点v拆分为两个顶点v‘和v'’，并在v‘和v'’之间添加一条具有顶点容量的边。在新图中，连接到v的所有边(即，v是其目的地)都应该与v‘相连，并且来自v的所有边都应该从新图中的v'’开始。

你可能知道，当你让流x-a-b-y 3时，你增加了反向边的容量。在这种情况下，您将添加边a x 3，b a 3，y b 3。如果您像我所描述的那样做图表示，您将看到在第一种情况下可以使用额外的流(我认为它可以通过x-a-d-c-b-y，但没有检查它)。

最短路径的选择不应该改变答案-正如我在评论中提到的那样，我们在每一步上只选择最短路径，以避免出现性能下降的糟糕情况，但答案总是相同的。

希望这个答案能有所帮助。