1

私自身、そしておそらく他の多くの人がここに固執していることを知っています。

さて、CLRS(3 版、22.4.2)によると、有向非巡回グラフの 2 つのノード間のすべての単純なパスを見つけるための O(n) アルゴリズムがあります。Number of paths between two nodes between two nodes in a DAGとAll the all the paths between 2 nodes in graphと同様の質問をしましたが、どちらの場合も、適切な説明や疑似コードが言及されていません。効率的なもの ( O(n))。

誰かが実際に取引を解決する1つの正確なコードまたは疑似コードを投稿できれば、上記のリンクをすべて調べたときに、背の高い単一の答えが実際には見つからなかったからです。

コードが巡回グラフも処理する場合、つまり、グラフに循環がある場合はより良いでしょうが、2 つのノード間のパスに循環が含まれていない場合、パスの数はFINITE にする必要があります。

4

1 に答える 1

7

Jeremiah Willcockの答えは正しいですが、詳細はわかりません。DAG の線形時間アルゴリズムを次に示します。

for each node v, initialize num_paths[v] = 0
let t be the destination and set num_paths[t] = 1
for each node v in reverse topological order (sinks before sources):
    for each successor w of v:
        set num_paths[v] = num_paths[v] + num_paths[w]
let s be the origin and return num_paths[s]

一般的な有向グラフの問題は#P-completeであると確信していますが、数分間の検索では、 cstheory に関するソースのない質問を除いて何も見つかりませんでした。

さて、ここにいくつかの擬似コードがあります。以前のアルゴリズムの内容をトポロジカル ソートに統合し、いくつかのサイクル検出ロジックを追加しました。sとの間のサイクルの場合t、 の値は不正確になる可能性がありますが、が到達可能num_pathsかどうかによってゼロ以外の値になります。tサイクル内のすべてのノードがin_cycletrue に設定されるわけではありませんが、すべての SCC ルート (Tarjan の SCC アルゴリズムの意味で) が true に設定されるため、s と t の間にサイクルがある場合にのみ早期終了をトリガーするのに十分です。

REVISED ALGORITHM

let the origin be s
let the destination be t
for each node v, initialize
    color[v] = WHITE
    num_paths[v] = 0
    in_cycle[v] = FALSE
num_paths[t] = 1
let P be an empty stack
push (ENTER, s) onto P
while P is not empty:
    pop (op, v) from P
    if op == ENTER:
        if color[v] == WHITE:
            color[v] = GRAY
            push (LEAVE, v) onto P
            for each successor w of v:
                push (ENTER, w) onto P
        else if color[v] == GRAY:
            in_cycle[v] = TRUE
    else:  # op == LEAVE
        color[v] = BLACK
        for each successor w of v:
            set num_paths[v] = num_paths[v] + num_paths[w]
        if num_paths[v] > 0 and in_cycle[v]:
            return infinity
return num_paths[s]
于 2012-06-19T17:08:59.967 に答える