c# - Dijkstra 算法扩展了额外的限制变量

Question

我在将其应用到我当前的寻路算法时遇到了问题。

目前我已经编写了 Dijkstra 并且可以正常工作，但我需要更进一步并添加一个限制(范围)。我可以用图片更好地解释:

假设我的范围是 80。我想从 A 转到 E。我当前的算法按预期工作，因此结果为 A->B-E。

但是，我只需要走权重不超过范围 - 80 的路径，这意味着 A->B->E 不是选项，但 A->C->D->B->E (考虑到范围/限制在每次停止时都会重置)

到目前为止，我已经实现了一个名为 Possible 的 bool，它将返回路径的单个部分(例如 A->B)与我的限制/范围相比是否可能。

我的主要问题是我不知道从哪里/如何开始。我唯一的想法是查看 Possible 在哪里 false (A->B 在总路线 A->B->E ) 并再次运行从 A 到 A->E 的算法，不包括/不包括 B 停止点/顶点。

这是一个好方法吗？因此，我的大 O 表示法会递增两次(据我所知)。

Answer 1

我看到了两种方法

1. 创建一个只包含 < 80 边的新图 G'，并在那里寻找最短路径...减少时间为 O(V+E)，另外 O(V+E) 内存使用

2. 你可以改变 Dijkstra 的算法，忽略大于 80 的边，只跳过大于 80 的边，当给相邻顶点赋值时，复杂度和内存使用在这种情况下保持不变