5

しばらくの間、ポイント A からポイント B への有向非巡回グラフの最大パスを見つけるために、複雑さ O(V + E) で実行されるアルゴリズムを使用しています。 A、および各ノードが持つ「親」(他のノードから来るエッジ) の数に注意してください。次に、BFS を実行しますが、すべての「親」を既に使用している場合にのみ、ノードを「アクティブ化」します。

queue <int> a
int paths[] ; //Number of paths that go to note i
int edge[][] ; //Edges of a
int mpath[] ; //max path from 0 to i (without counting the weight of i)
int weight[] ; //weight of each node

mpath[0] = 0

a.push(0)
while not empty(a)
    for i in edge[a]
        paths[i] += 1
        a.push(i)

while not empty(a)
    for i in children[a]
        mpath[i] = max(mpath[i], mpath[a] + weight[a]) ;

        paths[i] -= 1 ;
        if path[i] = 0
            a.push(i) ;

このアルゴリズムに特別な名前はありますか? 私はそれを情報学の教授に話しました.彼はそれを「DAGの最大パス」と呼んでいました.マキシマムパス」。

4

3 に答える 3

3

他の人が述べたように、これは単なる「DAGの最長パス」です。ただし、使用している手法は、実際には動的計画法を使用したトポロジカル ソートです。

于 2010-05-17T20:37:02.247 に答える
2

おそらくいいえ - それは一般的なアルゴリズムではないからです。DAG でパスを見つける必要がある場合は、それをソートし、1 回トラバースして最長パスを保持するだけです。

于 2010-05-17T05:54:31.290 に答える
1

DAG の最長パス? 必ず DAG について言及してください。一般的なグラフで最長経路を見つけることが NP 完全です。

于 2010-05-17T05:01:57.600 に答える