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 はこれを非巡回フロー問題と呼び、動的ツリーに関する彼らの最初の論文の 389 ページで O(m log n) 時間の解について説明しています。最速のアルゴリズムが必要ない場合は、深さ優先検索を繰り返し使用して 1 つのフロー サイクルを見つけ、1 つ以上のアークをキャンセルする最小量のフローを逆方向に送信します。

あなたのグラフで：

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

流れは非循環なので、停止します。