寻路：到目的地的多条路径，带边缘删除

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够不着）是不可能的，但在所有的最小图形计算