1樓：
不可以的，因為最長子路徑不滿足最優子結構。
假設源點是s，終點是t，我們先從「分治」（其實只有「治」）出發來思考。
假如最短路徑上有一點p，即s->...->p->...->t是最短路徑。
那麼s->...->p一定也是s->p的最短路徑（否則，如果有更短的，s->...->p->...
->t就不是最短的了，矛盾），同理p->...->t也是p->t的最短路徑。 然後，我們可以把這兩個子問題的策略合併成原問題的策略。
最短路徑問題的子問題的策略就是原問題最優策略的組成部分。
最長路徑就不一定了，比如有這樣乙個圖
A --(2)-- T
(13)
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
(13)
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-難的。
不知道我的大白話，題主理解了沒？
2樓：愛知
理論上講同等條件下定義的最短路和最長路是對偶的，比如無負邊的最短路就是無正邊的最長路的對偶問題。(類似的還有最大/最小生成樹)
具體求解時，只需要把圖中所有邊的權重取反，然後使用最短路的適當解法即可。
另外，有負環的最短簡單路和有正環的最長簡單路是NP-Hard的。
Ps. 簡單路徑：無重複的頂點路徑。
3樓：
話說這是我校演算法分析期末考試題來著……
證明最長路徑問題是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的
如何在最短的時間內搞定資料結構和演算法，應付面試
Kkkkeiraa 既然是應付面試，那麼可以這麼說，找到真題然後認真做出來，總結做題的過程，花費最小的代價，就可以成功搞定面試了。推薦題主乙個平台牛客題霸，它上面的真題，對知識點做了歸納，同時按不同難度進行了劃分，是十分適合作為面試籤突擊的刷題寶典。真題更新比較快，同時包含很多知名公司的題目，如果你...
資料結構可以怎樣運用到日常生活中呢？
算是乙個工作學習中的指導思想吧 貪心演算法通過數次區域性最優解累積出乙個不錯的總體解 面臨一堆雜亂無章的問題 選擇 不知道從何處開始處理實施時，直接上貪心法，第一時間去解決對個人發展收益最大的事情。在一次一次的選擇中累積起來，相信也能在大多數時候擁有乙個不錯 現狀 動態規劃需求全域性最優化，戰術家到...
考研資料可以用PDF 版本嗎？
雨過天青 2022任燕翔安全屋 知識體系與考試應用.pdf2022啟航王吉政治千題練 打卡冊.pdf2022啟航王吉政治千題練 解析分冊.pdf2022啟航王吉政治千題練 試題分冊.pdf2022孔昱力政治選擇題高分指南 習題分冊.pdf2022孔昱力政治選擇題高分指南 解析分冊.pdf2022徐濤...