最長路徑

Question

我怎樣才能在線性時間發現的圖像這樣的最長路徑：

3 - > 2

4 - > 3

2 - > 5

我知道這裏最長的路徑是4 - > 3 - > 2所以它有3個veticles，但我不知道如何在O（N）時間找到它。請幫忙。 預先感謝您。

Answer 1

頂部排序圖並按拓撲排序順序選擇頂點。

For each vertex u 
    For each edge (u,v) 
     if(d[v] < d[u] + weight(u,v)) 
      d[v] = d[u] + weight(u,v) 

其中，任何頂點u的d [u]是離源頭最遠的距離。對於每個頂點u，d [u]被初始化爲最小值，d [source] = 0。

由於它是一個DAG因此我們只需遍歷和放鬆每個邊緣一次。它基本上簡化了最長路徑的貝爾曼福特算法。