圖中的最長路徑問題怎麼算？

01-04

如圖圖是隨手畫的，數值也是隨手加的，這樣的圖，如何找到一條最長路徑，起點不限，終點不限(圖是有向圖，圖畫的不好，邊分別是A-&>B,B-&>C,C-&>D,A-&>C,B-&>D,A-&>D)
拓展到N個，這樣的圖用鄰接矩陣存，正好存滿矩陣的上三角或者下三角，這樣的問題最直接的思路是什麼？有什麼優化的辦法嗎？
我的思路如下：
1.選取一個頂點BFS，每次存下當前走一步後的路徑長度之和

（相當於創建了一棵樹，樹的每個節點的value = 當前節點到父節點的路徑長度 + 父節點的value ）
2.對每一個頂點，做1
3.在生成的所有的樹(N個節點必然會生成N棵樹)的所有節點中找到一個最大的，即是最終答案
請問我的思路是正確的嗎？有沒有其他的辦法？

如果圖裡有正權圈，那麼最長路徑是不存在的，或者說最長路徑是+無窮。

如果是無圈圖或者沒有正權圈，直接把邊權反號即可。這時候就變成一個最短路徑問題了是吧。

但是即使存在正權圈，我們也可以討論一些限定情況的最長路徑問題。比如我們討論如下兩個限定條件：

1、要求路徑無重複邊；

2、要求路徑無圈。

在第一個要求下，我們可以寫出mathematical programming：

max ∑c_ij x_ij （最大化邊權和）

滿足

∑x_ij - ∑x_jk = delta （流量保守約束）

x_ij € {0,1} （決策變數限制）

以上整數規劃是totally unimodular的，因此有polynomial time solvable algorithm.

對於第二個限制條件，可以寫出：

max ∑c_ij x_ij （最大化邊權和）

滿足

∑x_ij - ∑x_jk = delta （流量保守約束）

∑x_jk ＜= 1 （無圈約束）

x_ij € {0,1} （決策變數限制）

利用lagrangian relaxation把無圈約束dualize掉，問題就化為上一個問題。

因此這幾個問題其實都是很容易的。

由於手機碼字，公式都是隨意輸的，格式強迫症者見諒。

更正一下，上述兩個規劃有可能出現不在路徑上的正權圈。因此問題的解決應該還是要用到heuristics.在有正權圈的圖中求無圈最長路徑應該和TSP問題等價。

把距離取負值就是個最短路徑問題，有負權值的最短路徑不適用dijkstra演算法，但基於鬆弛技術的bellmanford和floyd演算法都是適用的，計算多點之間最短路徑使用floyd演算法，具體來說是進行n-2輪鬆弛，即對任意兩點窮舉第三點，並嘗試將距離替換成經由第三點的距離。完成後額外進行一輪鬆弛，如果距離繼續變小，說明存在負權有向環，最短路徑不存在（可以不斷沿著環繞），否則當前路徑就是最短路徑。

不過看題主的意思，這個圖有一個特殊特性，它的有向邊只能從編號小的通往編號大的，這就更簡單一些了，以某個點結束的路徑只能由編號比它小的頂點及這些頂點之間的邊決定，這是個動態規劃問題。可以如下表述：

$D[k] = max(max_{0 le j < k, (j,k) in E} D[j] + d(j,k), 0)$

其中D[k]為以頂點k結尾的最長路徑的長度，d(j,k)表示j和k之間有向邊的距離。如果用特殊的鄰接表（反向的鄰接表，邊按照終點組織）來表示圖，這是個O(E)複雜度的演算法，最後要求的答案就是D[k]的最大值。

DAG最長路或者最短路都可以用動態規劃；一般的帶權圖最長路是NP-hard的，沒有高效演算法。

堆優Bellman-Ford。連判正環也一併解決了。

題解：將數據取負，上spfa演算法。

無負權就取倒數然後亂搞？

有負權那bellman ford？

首先不能成環，因為成環會出現無限長的路徑。

不能成環的話就可以從前向後編號，動態規劃，詳情請百度『關鍵路徑』(Critical path)演算法。

有一種基於圖中節點拓撲序的最短路與最長路演算法，該演算法比狄傑斯特拉演算法效率高几個量級。

該演算法一般用在基於子網路的交通分配演算法上，具體論文你可以查閱R.B.Dial在2006年發在transportation research part B上的一篇大概叫path-based traffic assignment problem algorithm的文章。時間有點久了具體名字叫不上來了。

不過你的圖中有負權值，可能需要對權值預處理一下。

把點排好序，動態規劃即可。