最适合动态最大流计算的图算法/实现是什么？

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)更好？

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

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

我尝试理解所有标准算法，并思考如何修改它们，但由于图论并非我的领域，我失败了...

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

- Mokay2k

Answer 1

我能找到的有关这个问题的通用案例唯一的文章是Kumar和Gupta发表的“最大流问题的增量算法”，链接为https://doi.org/10.1023/A:1023607406540，但需要付费才能查看。主要思路很简单：当我们增加弧uv的容量时，在具有剩余正容量的连通弧和uv的图中从s到t的路径上搜索所有顶点w（从u反向遍历，从v正向遍历）。从之前计算出的流开始，在这些顶点上运行Goldberg-Tarjan算法。

首先将弧容量设为零然后再增加它来添加弧。Kumar-Gupta 还考虑了降低容量/删除弧的情况。这更加复杂。他们从t向v推送流，然后删除v，然后再向前推送流。

- bar

Answer 2

你已经在使用任何库了吗？如果我是你，我至少会查找一个实现网络单纯形的库。

- hugomg