我必须编写一个程序,该程序需要在有向流程图中维护一些数据。我需要在运行时计算最大流量。
我知道存在多个用于处理图的库,几乎实现了所有经典算法,但我的问题是我的图是动态的,这意味着它会在运行时演变。每次进化后,我都需要重新计算新的最大流量。
进化是:
- 添加边缘
- 增加边缘的容量
我需要重新计算的是从源 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) 更好的想法?
如果我也考虑这种可能的演变呢?
- 删除一个节点(以及该节点的所有传入/传出边)
我试图理解所有标准算法并思考如何修改它们,但由于图论不完全是我的领域,我惨遭失败......
任何帮助将不胜感激。谢谢。