gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:29:54 25 4
gpt4 key购买 nike

图算法题给你。

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

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

谢谢!

最佳答案

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

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

关于algorithm - 找到所有短于给定距离的备选路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18668374/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com