动态最大流计算的最佳图算法/实现

Question

我必须编写一个程序，需要在有向流程图中维护一些数据。我需要计算运行时的最大流量。

我知道有几个用于处理图的库，实现了几乎所有经典算法，但我的问题是我的图是动态的，这意味着它在运行时演变。每次进化之后，我都需要重新计算新的最大流量。

进化是：

• 添加一条边，
• 增加一条边的容量

，而我需要重新计算的是在该步骤中修改的边从源 S 到目标节点的最大流量。例如：

                     S                            S  
                     |                            |
                     5                            5
                     |                            |
                     V                            V
                     A---3--->B                   A---5--->B
    adding edge      |        |     increasing    |        |
      B-->D          2        1      A-->B of     2        1
                     |        |     two units     |        |
                     V        V                   V        V
                     C---3--->D                   C---3--->D

                      OUTPUT: 3                    OUTPUT: 5  
                    (maxflow S-D)                (maxflow S-B)

考虑到我的图中演化的非常具体的性质，哪种算法/库的时间性能更好？我的意思是，考虑到每一步的图几乎与上一步相同（除了一条边），是否有一种算法可以有效地重用之前计算的中间结果？

我知道每次目的地都不同这一事实使问题有点困难......知道我如何在每一步都比 O(VE^2) 更好吗？

如果我也考虑这种可能的演变呢？

• 删除一个节点（以及该节点的所有传入/传出边缘）

我试图理解所有标准算法并思考如何修改它们，但是图论不完全是我的领域，我惨败了......

任何帮助将不胜感激。 谢谢。

Answer 1

我能找到的关于此问题一般情况的唯一文章是最大流问题的增量算法，作者：Kumar 和 Gupta。它位于付费墙后面，但主要思想非常简单。当我们增加弧uv的容量时，遍历图形两次以找到位于从s到的路径上的所有顶点w图中的 t 具有正剩余容量和 uv 的弧。 （从 u 向后遍历，从 v 向前遍历。）从之前计算的流开始，在这些顶点上运行 Goldberg-Tarjan。

要添加弧线，首先添加其容量为零，然后增加其容量。库马尔-古普塔还考虑了减少容量/移除电弧。这个比较复杂；他们将流从t推回到v，然后删除v，然后再次将流向前推。

Answer 2

您有正在使用的图书馆吗？如果我是你，我至少会寻找一个实现网络单工的解决方案。