稀疏循環圖中最長的簡單路徑

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）），因爲當您添加新的可能路線時，經過每個節點/頂點的路線呈指數級增長。

編輯：我錯過了一個細節，你要求的平均時間複雜度將意味着攤銷複雜性。但是，由於你的算法總是評估所有可能的路徑，所以最壞情況的複雜度與平均複雜度相同。