将加权有环图转换为等效无环图

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

例如：路径如下，

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 方面是等效的。

谢谢， 维韦克

Sleator–Tarjan 将其称为非循环流问题，并在其论文第 389 页上描述了 O(m log n) 时间解决方案第一篇关于动态树的论文 http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf。如果不需要最快的算法，请重复使用深度优先搜索来查找一个流周期，然后反向发送取消一个或多个弧的最小流量。

在你的图表上：

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. Send -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

流动是非循环的，所以我们停下来。