我得到一个流网络 G 和它们的（边缘）容量和（边缘）流过每个边缘，还有一个流 F。我想检查残差图中是否存在从源到目标的路径以便找到如果 F 是最大流量，则输出。
是否有可能在 O(E) 时间内完成？
有人可以给我一些帮助吗，也许表明我应该这样做？
- 已编辑
问问题
733 次
2 回答
0
BFS 可用于在残差图中查找路径。运行 BFS 需要 O(|E|+|V|) 运行时间。在流网络中，所有顶点都是连接的，因此，顶点的数量不大于边数的两倍。有了这些信息，运行 BFS 以在残差图中查找路径的复杂度为 O(|E|)
于 2020-12-01T13:38:33.410 回答
0
我得到一个流网络 G 和它们的（边缘）容量和（边缘）流过每个边缘。我想检查是否存在从源到目标的路径。
如果您只想检查是否存在从源到目标的路径，则不需要残差图。
如果我有残差图，那么我只需对 BFS 算法进行一些调整，以检查是否存在这样的路径，很容易。我发现这可以在 O(|E|) 中完成。
BFS算法的时间复杂度是O(V+E)，不是O(E)。
但是我没有残差图所以我的问题是是否应该先计算它然后继续，如果是这样，它会增加我的整体时间复杂度 O(|E|)？
计算残差图应该比O(V+E).
如果你试图解决最大流量问题，你为什么不使用标准算法，比如时间复杂度为 的福特-富尔克森算法O(E max|f|)？
更新
我想检查残差图中是否存在从源到目标的路径，以确定 F 是否为最大流量。是否有可能在 O(E) 时间内完成？
要检查有向图中的两个节点之间是否存在路径，您应该需要O(V+E)时间。正如您之前在问题中提到的那样，您可以使用 BFS 或 DFS。
于 2017-02-19T22:00:58.503 回答