尋路：到目的地的多條路徑，帶邊緣刪除

Question

我有一個奇怪的尋路問題。在下圖中，有兩種邊緣 - 紅色和藍色。紅邊是可靠的，而藍邊不是 - 它們提供了快捷方式，但在某些情況下可能會消失或無法使用 - 您可以將它們想象爲冬季下雪的山路，或週末不運行的渡口，或僅在上下班時間運行的列車線路。

我希望我的探路者能夠選擇可能的路徑。用戶必須知道到達目的地的最快速度不可靠的方式，以及如果該路徑不可用，可能的替代方案。探路者應該產生最短路線（在圖中，使用藍色邊緣'b'進行3次跳躍），以及最短的可靠路線 - （5跳，僅使用紅色邊緣）以及所有其他可能路線短於可靠路線並利用不可靠的藍色邊緣。

對於該圖中，這些都是可能的排列：

• 是3周跳，使用邊緣 'B'
• 是3跳，使用邊緣 '一個'， 'd'
• 4跳，使用邊緣'c'
• 4跳，使用邊緣'a'
• 4跳，使用邊緣'd'
周
• 5跳，只用紅邊

我對這個算法的第一次嘗試如下：

1. 查找&保存最短的路徑（使用廣度優先搜索）
2. 如果有停止路徑中沒有藍色邊緣。
3. 如果有路徑藍色邊，取出第一個和去1

然而，這種算法是不完整的，因爲它會錯過一些可能的路徑。在上面的示例中，僅使用邊a的路徑將被忽略（所有其他路徑將被包括在內）。

我的下一個想法是運行搜索每個可能的藍色邊緣組合：[a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d]。當然，這是非常低效的，可能不適合大量的藍色邊緣。

---

你能想出任何解決方案，可以幫助我在這裏嗎？我需要一個：

• 一種有效的方法來計算所有可能的路徑
• ，在最短的順序返回路徑最長

前者是最好的解決方案的算法，但後來我可以跑10秒，然後至少返回一個很好的短路徑選擇到目的地。順便提一句，我對圖的大小有一個很好的想法：有大約7000個頂點，30,000個紅色邊和200個藍色邊。

我確信這種問題以前已經考慮過了，但是我找不到任何關於它的文章。你能爲我指出正確的方向嗎？

Answer 1

，我可以看到它，你可以分割你的問題分爲兩個部分：

1. 獲取最短可靠路徑 - 這可以從圖中移除所有的藍邊來完成，並運行任何最短路徑算法（如Dijkstra's Algorithm）。
2. 獲得k最短的不可靠路徑 - 這是未修改的圖上的K shortest paths problem，您需要選擇k。更大的k是 - 更廣闊的它將是生成路徑。

需要注意的是找出所有可能的路徑是非常低效的，因爲有那些階乘數，而且這個數字往往會（7000個節點definetly夠不着）是不可能的，但在所有的最小圖形計算