路径查找:到达目标的多条路径，并去除边缘

Question

我有个奇怪的寻路问题。在下图中，有两种边缘--红色和蓝色。红色边缘是可靠的，而蓝色边缘则不是--它们提供快捷方式，但在某些情况下可能消失或不可用--你可以把它们想象成在冬天会被雪覆盖的山路，或者是周末不营业的渡口，或者只有通勤时间才能运行的火车线路。

我想让我的探索者产生一个可能的路径选择。用户必须知道到达目的地的最快、不可靠的方式，如果无法使用该路径，则必须知道可能的替代方案。探路者应该产生最短的路径(在图中，3跳使用蓝色边缘'b')，最短的可靠路由- (5跳，仅使用红色边缘)，以及所有其他可能的路由都比可靠的路由短，并利用不可靠的蓝色边缘。

​

​

对于图表，以下是可能的排列：

• 3跳，使用边缘'b‘
• 3跳，使用边'a'，'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. 获得最短的可靠路径-这可以通过从图中删除所有蓝色边来完成，并运行任何最短路径算法(如迪克斯特拉算法)。
2. 获取k条最短的不可靠路径--这是未经修改的图上的K-最短路径问题，您需要选择您的k。更大的k是--它将产生更多的路径。

请注意，找出所有可能的路径都是极其低效的，因为有这些路径的阶乘数，而且在所有的最小图中都不可能计算这个数(对于7,000个节点来说，这是绝对无法达到的)。