algorithm - 找到所有短于给定距离的备选路径

Question

图算法题给你。

我有一张图，用来表示道路网络。所以其中有循环(环形交叉路口是微不足道的)。还有一些边缘是双向的，有些是单向的(单向街道)。边按其长度加权。

假设我有两个节点并且已经计算出它们之间的最短路径。我想做的是找到连接两个节点的所有其他路径，这些路径短于某个距离 X。将这些路径称为“备用”。

下面是一个 ascii 艺术的例子，我用字母标记了边，用数字标记了节点。

         F
      5----6  
   E /      \ G  
    3--------4
   /    D     \
B /            \ C
 1--------------2
        A              

假设我有从 1->2 覆盖边 A 的路径，我想找到替代路径。该路径的一个替代方法是 BDC，前提是它的长度小于 X。BEFGC 是另一个。

另一个示例路径是连接节点 1->4 的 BD。另一个替代方案是 AC。

更多要求:

1. 备用路径不应包含主路径的任何部分。因此，如果主路径是 A，则包含 A 的任何替代路径都不是有效的替代路径。在上面连接 1->4 的 BD 示例中，BEFG 不是有效的替代，因为它包括主路径中的 B。
2. 替补不应有内部循环。例如，这条备用路径不允许连接 1->2:BDGFEDC，因为它穿过边 D 两次。

谢谢!

Answer 1

如果您运行 Dijkstra 算法来寻找最短路径，您将得到一个表，其中为每个节点提供了从源到该节点的最短距离。我会从图中删除最短路径上的点，运行 Dijkstra 算法，然后从目标开始进行深度优先搜索，每次你当前正在调查的路径成为一个循环时终止搜索，或者距离的总和当前节点到源点的路径和最短距离大于X。

每次实际到达源节点时，您都​​可以打印出到目前为止的路径。