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位于从st的路径上,弧的剩余容量和uv为正。(从u向后遍历,从v向前遍历。)从先前计算的流开始,在这些顶点上运行 Goldberg-Tarjan。

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

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

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

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