algorithm - 将加权直接循环图转换为等效的无环图

Question

我有一个循环加权有向图，目标是删除路径中存在的循环。

例如:路径如下，

from | to | weight
------------------
a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

图中的循环是由路径d -> a引入的。任何人都可以建议一种算法来通过调整其他节点的权重来删除循环 d -> a 。生成的无环图在将权重传递给端节点 e、f 方面是等价的。

谢谢， 维维克

Answer 1

Sleator–Tarjan 将其称为非循环流问题，并在其 first paper on dynamic trees 的第 389 页描述了一个 O(m log n) 时间的解决方案.如果您不需要最快的算法，请重复使用深度优先搜索找到一个流量循环，然后反向发送取消一个或多个弧的最小流量。

在你的图表上:

a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

DFS 找到一个循环 a -0.5> b -1> d -0.25> a。在同一周期发送 -0.25。

a    -> b | 0.5 - 0.25 = 0.25
a    -> c | 0.5
c    -> e | 1
b    -> d | 1 - 0.25 = 0.75
d    -> f | 0.75

我们删除

d    -> a | 0.25 - 0.25 = 0

流程是非循环的，所以我们停止。