我有一个奇怪的寻路问题 . 在下图中，有两种边 - 红色和蓝色 . 红色边缘是可靠的，而蓝色边缘不是 - 它们提供快捷方式，但在某些情况下可能会消失或无法使用 - 您可以将它们视为冬季下雪的山口，或者周末不运行的渡口，或训练仅在通勤时间运行的线路 .
我希望我的探路者能够产生一系列可能的路径 . 用户必须知道到达目的地的最快的不可靠方式，以及如果该路径不可用的可能替代方案 . 探路者应该产生最短的路线（在图中，使用蓝色边缘'b'的3个跳跃）和最短的可靠路线 - （5个跳跃，仅使用红色边缘）以及比可靠路线短的所有其他可能路线并利用不可靠的蓝色边缘 .
对于图表，这些是可能的排列：
-
3个跃点，使用边缘'b'
-
3次跳跃，使用边缘'a'，'d'
-
4个跃点，使用边缘'c'
-
4个跃点，使用边缘'a'
-
4个跃点，使用边缘'd'
-
5个跃点，仅使用红色边缘
我对此算法的第一次尝试如下：
-
查找并保存最短路径（使用广度优先搜索）
-
如果路径中没有蓝色边缘，请停止 .
-
如果路径中有蓝色边缘，请删除第一个边缘并转到1 .
但是，此算法并不完整，因为它可能会遗漏一些可能的路径 . 在上面的示例中，将仅丢失仅使用边缘“a”的路径（将包括所有其他路径 . ）
我的下一个想法是搜索每个可能的蓝色边缘组合： [a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d] . 当然，这是非常低效的，并且对于大量的蓝色边缘可能不可行 .
您能想到任何可以帮助我的解决方案吗？我需要一个：
-
计算所有可能路径的有效方法
-
以最短到最长的顺序返回路径的算法
前者是最好的解决方案，但后者我可以跑，比如10秒，然后至少返回到目的地的一小段短路径 .
顺便说一下，我对图表的大小非常了解：大约有7000个顶点，30,000个红色边缘和200个蓝色边缘 .
我确定之前已经考虑过这种问题，但我找不到任何关于它的文章 . 你能为我指出正确的方向吗？
1 回答
正如我所看到的，您可以将问题分成两部分：
获取最短的可靠路径 - 可以通过从图中删除所有蓝色边缘来完成，并运行任何最短路径算法（例如Dijkstra's Algorithm） .
获取k个最短的不可靠路径 - 这是未修改图表上的K shortest paths problem，您需要选择
k. 更大的k- 更广泛的是生成路径 .请注意，找到所有可能的路径是非常低效的，因为存在这些路径的因子数，并且除了最小的图之外，所有这些数字往往无法计算（对于7,000个节点而言绝对无法实现）