0

图算法问题给你。

我有一个图表，用于表示道路网络。所以它里面有循环（一个环形交叉路口是微不足道的）。还有一些边缘是双向的，一些是单向的（单向街道）。边按其长度加权。

假设我有两个节点并且已经计算出它们之间的最短路径。我想做的是找到连接两个节点的所有其他路径，这些路径小于某个距离 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 的替代品是 AC。

更多要求：

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

谢谢！

4

1 回答 1

1

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

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

于 2013-09-07T05:14:30.297 回答