图算法问题给你。
我有一个图表,用于表示道路网络。所以它里面有循环(一个环形交叉路口是微不足道的)。还有一些边缘是双向的,一些是单向的(单向街道)。边按其长度加权。
假设我有两个节点并且已经计算出它们之间的最短路径。我想做的是找到连接两个节点的所有其他路径,这些路径小于某个距离 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。
更多要求:
- 替代不应该包括主路径的任何部分。因此,如果主路径是 A,则任何包含 A 的替代都不是有效的替代。在上面连接 1->4 的 BD 示例中,BEFG 不是有效的备用路径,因为它包括位于主路径中的 B。
- 替代品不应该有内部循环。例如,连接 1->2: BDGFEDC 不允许这条备用路径,因为它两次遍历边 D。
谢谢!