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

pathfinding: multiple paths to a destination, with edge removal

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

我希望我的探路者产生一系列可能的路径。用户必须知道到达目的地的最快的不可靠方式，以及如果该路径不可用时可能的替代方案。探路者应该产生最短路线（在图中，3 跳使用蓝色边 'b'），和最短的可靠路径 -（5 跳，仅使用红色边）以及所有其他可能的比可靠的路线并利用不可靠的蓝色边缘。

对于图表，这些是可能的排列：

我对这个算法的第一次尝试如下：

  1. 查找并保存最短路径（使用广度优先搜索）
  2. 如果路径中没有蓝色边缘，则停止。
  3. 如果路径中有蓝色边，移除第一个并转到 1。

但是，此算法并不完整，因为它可能会遗漏一些可能的路径。在上面的示例中，将错过仅使用边缘 'a' 的路径（将包括所有其他路径。）

我的下一个想法是 运行 搜索所有可能的蓝色边缘组合：[a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d]。当然，这是非常低效的，并且对于大量的蓝色边缘可能不可行。

你能想出任何可以帮助我解决这个问题的解决方案吗？我需要其中之一：

前者是最好的解决方案，但后者我可以 运行 比如说 10 秒，然后 return 至少可以选择到目的地的短路径。

顺便说一句，我很清楚我的图的大小：大约有 7000 个顶点、30,000 条红色边和 200 条蓝色边。

我敢肯定之前已经考虑过这种问题，但是我找不到任何关于它的文章。你能给我指出正确的方向吗？

据我所知，您可以将问题分为两部分：

  1. 获取最短可靠路径 - 这可以通过从图中删除所有蓝色边和 运行 任何最短路径算法（例如 Dijkstra's Algorithm）来完成。
  2. 获取 k 条最短不可靠路径 - 这是未修改图上的 K shortest paths problem，您需要选择 k。 k 越大 - 生成路径的范围就越大。

请注意，找到所有可能的路径是非常低效的，因为存在这些路径的阶乘数，并且除了最小的图（对于 7,000 个节点来说绝对无法计算）之外，这个数字往往无法计算