數據結構：可以用求最短路徑的方法思想求最長路徑么？為什麼呢？

01-03

這裡求解最短路徑的通用方法有Dijkstra演算法和Floyd-Warshall演算法，Dijkstra演算法不允許邊的權值為負，也不允許有迴路，而Floyd-Warshall演算法可以允許邊的權值為負，但不允許有迴路。
感覺都有局限，這兩種演算法的思想可以用來求最長路徑么？？
為什麼不可以？能舉個反例么？？？？

不可以，核心在於最短路問題是有最優子結構的，就是『最短路的子路徑還是最短路』，而最長路徑不存在這個子結構。

話說這是我校演算法分析期末考試題來著……

證明最長路徑問題是NP-Hard的

Proof:假如最長路徑問題有多項式時間演算法A，我們證明Hamilton迴路問題也有多項式時間演算法，從而建立Turing歸約。

對任意一個圖G=&，用如下演算法檢查其是否有Hamilton迴路：

給所有邊賦權值1，取定V中一個頂點v

對所有v "∈V,循環：

如果&∈E 且 v 到v "的最長路徑長度=|V|-1(用A計算)

那麼G有Hamilton迴路;

結束循環

如果所有v " 均不滿足上述條件，則G沒有Hamilton迴路;

很明顯，如果演算法A是多項式時間的，那麼上述Hamilton迴路問題的演算法也是多項式時間的，從而最長路徑問題是NP-Hard的

不可以。最短路徑問題是P的，但最長路徑問題是NP-hard的。見Longest path problem。

floyed演算法可以有迴路，但是不能有負權迴路

最長路問題分成兩種：

1. 可以走重複邊

2. 不能走重複邊

如果是1的話，那麼如果圖中有一條權為正的環，那麼你沿著環反覆走就得到無限長的路了，而如果沒有這樣的環的話，Bellman–Ford（單源）或者Floyed（任意點對）演算法都可以計算出正確的解

2的話是NP-Hard

不可以的，因為最長子路徑不滿足最優子結構。

假設源點是s，終點是t，我們先從「分治」（其實只有「治」）出發來思考。

假如最短路徑上有一點p，即s-&>...-&>p-&>...-&>t是最短路徑。那麼s-&>...-&>p一定也是s-&>p的最短路徑（否則，如果有更短的，s-&>...-&>p-&>...-&>t就不是最短的了，矛盾），同理p-&>...-&>t也是p-&>t的最短路徑。然後，我們可以把這兩個子問題的策略合併成原問題的策略。

最短路徑問題的子問題的策略就是原問題最優策略的組成部分。

最長路徑就不一定了，比如有這樣一個圖

A --(2)-- T

| |

(1) (3)

| |

S--(1)-- B

四邊形，括弧中的數是邊長.顯然S-&>T的最短路徑是S-&>A-&>T。把他拆成兩部分，S-&>A是S到A的最短路，A-&>T也是A到T的最短路，原問題的最短路，拆開來看也是子問題的最短路。

最長路徑是不滿足了。最長簡單路徑是S-&>B-&>T。但是S-&>B不是S到B的最長路徑，最長的是S-&>A-&>T-&>B。不滿足子結構的性質。

這會造成什麼後果呢？我們看具體演算法。

先看迪傑斯特拉。

迪傑斯特拉的思想通俗地說，是從源點開始，不斷「刷低上限」，直到刷完終點。初始S點集為源點，把S中標籤最小的點拿出來，刷低一遍他的所有臨點的上限。已經「刷緊」的點不能再刷，所有點的上限被充分「刷緊」，就刷完了。迪傑斯特拉能這麼干，是因為，已經刷緊的點確實不用再刷了。因為迪傑斯特拉是一種變相寬搜，能早刷到的都「刷緊」了，怎麼可能繞一圈以後還有更短的呢？

如果把迪傑斯特拉思想套在最長路徑會出什麼問題呢？看例子：

A --(2)-- B

| |

(1) (3)

| |

S--(1)-- T

S先把A刷成1，T刷成1。然後T把B刷成4，T的所有臨點都刷過了，T不再刷，於是得出了錯誤結論：T的最長路徑長是1. 其實S刷完A，A再刷完B，B再刷了T，這才是最長的。因此，迪不適用。

又問，那把迪演算法的「臨點刷完的點不能再被刷」這條去掉不就行了？不行，因為去掉的話，效率上的意義就不復存在了，相當於原始的搜索而已。迪之所以為正確演算法，是因為可以一步一步的根據子問題推算下來；之所以是高效的，是因為可以刷完臨點就不用再刷。再抽象一下，動態規劃類演算法之所以是正確的，是因為最優子結構與無後效性；之所以高效，是因為這種推算可以不重複計算字問題。

再看另一種思路的演算法，Bellman-Ford和SPFA。

SPFA通俗的說，就是從源點開始「刷」低上限，「被刷低」上限的點進隊列準備下一輪去刷別人，不斷的把「被刷低」的點的臨點也刷一遍，直到無點可刷；如果某個點n進宮，說明他在負權迴路上。Bellman-Ford想法更簡單，由於n個點的圖，路徑長度最多n-1，我們只要一步步的求這些結果就行了：假設最短路徑長度不超過1的情況、假設最短路徑長度不超過2的情況、假設最短路徑長度不超過3的情況... 假設最短路徑長度不超過n-1的情況。所以循環n-1遍，每遍把所有邊的端點刷一遍就OK了，因為長度不超過k的最短路徑，在k步內都能刷出來。如果n-1次刷完，還有能刷的，就肯定有負權迴路。

Bellman-Ford，用在最長路徑是顯而易見的不行，一條雙向的邊的兩個端點，能互刷，互擼個沒完沒了，沒辦法一步步的刷下去。

總結：因為最長子路徑問題，1. 不滿足最優子結構，所以不能一步步的推算； 2. 如果我們不一步步推了，只要有兩個狀態可以轉移，就通通遞推下去，那麼問題蛻化成了暴力搜索，是NP-難的。

不知道我的大白話，題主理解了沒？

不考慮環的情況下可以邊取負數用Bellman-Ford,這個演算法本身也可以檢查是否有環。

理論上講同等條件下定義的最短路和最長路是對偶的，比如無負邊的最短路就是無正邊的最長路的對偶問題。(類似的還有最大/最小生成樹)

具體求解時，只需要把圖中所有邊的權重取反，然後使用最短路的適當解法即可。

另外，有負環的最短簡單路和有正環的最長簡單路是NP-Hard的。

Ps. 簡單路徑：無重複的頂點路徑。

可以先找到最短，刪了，接著找，最後刪除的就是最長嗎？

把邊權取負一下，然後跑 Bellman-Ford ，為什麼不行？