4

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

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

进化是：

  • 添加边缘
  • 增加边缘的容量

我需要重新计算的是从源 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) 更好的想法？

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

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

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

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

4

2 回答 2

3

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

要添加弧，首先将其添加为容量为零，然后增加其容量。Kumar-Gupta 还考虑了降低容量/消除电弧。这更复杂；他们将流从t推回v，然后删除v，然后再次向前推流。

于 2011-07-19T23:13:57.950 回答
0

你有任何已经在使用的库吗？如果我是你，我至少会搜索一个实现网络单工的。

于 2011-07-19T17:46:38.423 回答