最長最短路徑（不完全）

Question

對於我的學士論文，我遇到了以下問題（解決這個問題可能對論文的實際問題有用）。我有一個加權有向圖G頂點V和V兩個頂點，開始s和目的地t。我可以刪除至多k頂點。我需要找到頂點，刪除頂點將使調整圖中從s到t的最短路徑的成本（長度）最大化。

我想，這個問題本來應該在文獻中討論過，但是，我沒有設法找到相關的文章。我會很感激有關文獻的任何鏈接。

Answer 1

您可以申請Yen's Algorithm找到最短的K路徑。現在你如何在你的代碼中應用它？您不適用於第一個K路徑，而是適用於所有與最短路徑長度相同的路徑。一旦你找到所有這些（K1作爲一個計數），你現在採取每個路徑並刪除（模擬你刪除）一個頂點（如果你已經認爲你可以跳過它），但如果沒有，現在你有一個問題最短路徑帶有可跳過頂點的圖形。在每一步中，您都嘗試最大化「最短路徑」並選擇該頂點。我正在考慮一種更優化的方式，但這是我從頭到尾所能做到的最好的方式。

你做K次：正如我所說的修改

1. 待辦事項日元的算法。
2. 找到刪除一個頂點以增加最小距離的最佳局部解決方案。