疎循環グラフ内で最も長い単純パス

Question

与えられます：任意の数のサイクルを含むことができる重み付けされていない有向グラフ（G =（E、V））です。

目標：すべての頂点のために、私はV

アルゴリズムのアイデアで、いくつかのターゲット頂点Xに最長の単純なパスをしたい：

For each v in V 
    v.distanceToTarget = DepthFirstSearch(v) 
Next 

DepthFirstSearch(v as Vertex) 
    if v = target then 
    'Distance towards target is 0 for target itself 
    return 0 
    elseif v.isVisitedInCurrentDFSPath then 
    'Cycle found -> I wont find the target when I go around in cycles -> abort 
    return -infinity 
    else 
    'Return the maximum Distance of all Successors + 1 
    return max(v.Successors.ForEach(Function(v) DepthFirstSearch(v))) + 1 
    end if 

は、すべてのケースのために、この正しいですか？ （すべての頂点からターゲットに到達できると仮定します）

グラフの辺の数は非常に少ないです。 仮定| E | < = 3 * | V |保持する。どのように平均時間の複雑さを計算するのですか？

ありがとうございます！

Answer 1

時間の複雑さは、ランタイムに最も影響を与える値です。あなたの場合、vとターゲットの間のすべての可能な経路を評価する。基本的にはO（ルート数）です。今度は、EとVのすべての可能なルートの数を表現する方法を理解する必要があります。

O（exp（E））またはO（exp（V））の可能性が高い結果は、新しい可能なルートを追加すると、各ノード/頂点を通過するルートが指数関数的に増加します。

編集：煩雑な償却を意味する平均的な時間の複雑さを求めていたという細部を見落としました。しかし、あなたのアルゴリズムは常にすべての可能な経路を評価するので、最悪の複雑さは平均的な複雑さと同じです。