最長路徑問題是在給定圖中找到最大長度的簡單路徑的問題。 如果路徑沒有任何重複的頂點，則稱為簡單路徑; 路徑的長度可以通過其邊數來測量，或者（在加權圖中）通過其邊緣的權重之和來測量。 與可以在沒有負權重循環的圖中的多項式時間中求解的最短路徑問題相比，最長路徑問題是NP難的，這意味著除非P = NP，否則它不能在任意圖的多項式時間內求解。 還已知更強的硬度結果，表明難以近似。 然而，它具有有向無環圖的線性時間解，它在尋找調度問題的關鍵路徑方面具有重要的套用。
基本介紹
- 中文名：最長路徑問題
- 外文名：Longest path problem
NP-HARD,非循環圖和關鍵路徑,特殊類別的圖表,參數化複雜性,
NP-HARD
可以使用哈密頓路徑問題的減少來顯示未加權最長路徑問題的NP-hard：若且唯若其最長路徑具有長度n-1時，圖G具有哈密頓路徑，其中n是頂點的數量。 G.由於哈密頓路徑問題是NP完全的，這種減少表明最長路徑問題的決策版本也是NP完全的。在該決策問題中，輸入是圖G和數k;如果G包含k個或更多邊的路徑，則所需的輸出為“是”，否則為無。
如果可以在多項式時間內解決最長路徑問題，則可以通過找到最長路徑然後將其長度與數字k進行比較來將其用於解決該決策問題。因此，最長的路徑問題是NP難的。問題“在給定圖中是否存在具有至少k個邊的簡單路徑”是NP完全的。
在具有非負邊緣權重的加權完整圖中，加權最長路徑問題與旅行推銷員路徑問題相同，因為最長路徑總是包括所有頂點。
非循環圖和關鍵路徑
在加權圖G中兩個給定頂點s和t之間的最長路徑與通過將每個權重改變為其否定而從G導出的圖-G中的最短路徑相同。因此，如果在-G中找到最短路徑，則在G中也可以找到最長路徑。
對於大多數圖形，此變換無用，因為它在-G中創建負長度的循環。但是如果G是有向非循環圖，則不能創建負循環，並且通過對-G中的最短路徑套用線性時間算法，可以線上性時間中找到G中的最長路徑，其也是有向無環圖。例如，對於給定DAG中的每個頂點v，可以通過以下步驟獲得以v結尾的最長路徑的長度：
1、找到給定DAG的拓撲排序。
2、對於DAG的每個頂點v，在拓撲排序中，通過查看其傳入的鄰居並將這一個鄰居記錄的最大長度加1來計算以v結尾的最長路徑的長度。如果v沒有傳入的鄰居，則將以v結尾的最長路徑的長度設定為零。在任何一種情況下，記錄此數字，以便算法的後續步驟可以訪問它。
完成此操作後，可以通過從具有最大記錄值的頂點v開始，然後重複地向後踩到具有最大記錄值的傳入鄰居，並反轉在這條路。
用於調度一組活動的關鍵路徑方法涉及構造有向無環圖，其中頂點表示項目里程碑，邊表示必須在一個里程碑之後和另一個里程碑之前執行的活動;通過估計相應活動將完成所花費的時間來對每個邊緣進行加權。在這樣的圖表中，從第一個里程碑到最後一個里程碑的最長路徑是關鍵路徑，它描述了完成項目的總時間。
有向無環圖的最長路徑也可以套用於分層圖繪製中：將有向非循環圖G的每個頂點v分配給其數量是以v結尾的最長路徑的長度的層，導致G的層分配最小可能的層數。
特殊類別的圖表
Dijkstra在20世紀60年代提出了一種用於在樹中找到最長路徑的線性時間算法，而該算法的形式證明於2002年出版。此外，最長路徑可以在加權樹上的多項式時間，塊圖，cacti，上的二分置換圖，和托勒密圖上計算。
對於區間圖類，已知O（n4）時間算法，其使用動態編程方法。這種動態規劃方法已被用於獲得更大類圓弧圖和共同可比性圖（即可比性圖的補充，也包含置換圖）的多項式時間算法，兩者具有相同的運行時間O（n 4）。後一種算法基於共同可比性圖的詞典深度優先搜尋（LDFS）頂點排序的特殊屬性。對於共同可比性圖，還已知具有較高運行時間O（n7）的替代多項式時間算法，其基於由輸入協同可比性圖的補充定義的部分有序集的Hasse圖。
此外，最長路徑問題可以在具有有界樹寬或有界團寬的任何類圖的多項式時間內解決，例如距離-遺傳圖。最後，在哈密頓路徑問題是NP難的所有圖類上顯然是NP難的，例如在分裂圖，圓圖和平面圖上。
參數化複雜性
當通過路徑長度參數化時，最長路徑問題是固定參數易處理的。例如，它可以通過執行以下步驟的算法在輸入圖形的大小上按時間線性求解（但在路徑長度上呈指數）：
執行圖表的深度優先搜尋。設d是得到的深度優先搜尋樹的深度。
使用深度優先搜尋樹的根到葉路徑的順序，按照搜尋遍歷的順序，構建圖的路徑分解，路徑寬度為d。
將動態編程套用於此路徑分解以找到時間上最長的路徑
，其中n是圖中頂點的數量。
由於輸出路徑的長度至少與d一樣大，因此運行時間也受
的限制，其中l是最長路徑的長度。使用顏色編碼，可以將對路徑長度的依賴性降低到單指數。類似的動態編程技術表明，當通過圖的樹寬參數化時，最長路徑問題也是固定參數易處理的。
對於有界集團寬度的圖，最長路徑也可以通過多項式時間動態規划算法求解。但是，多項式的指數取決於圖的clique-width，因此該算法不是固定參數易處理的。由clique-width參數化的最長路徑問題對於參數化複雜度類W 來說很難，表明固定參數易處理算法不太可能存在。
