3

这是我的问题的可视化。

在此处输入图像描述

我一直在尝试使用 djikstra，但是它没有用。

4

3 回答 3

2

在我看来，复杂之处在于 Dijkstra 的算法会丢弃您需要保留的信息：如果您试图从 A 到 E

   B
 /   \
A     D - E
 \   /
   C

而且 ABD 比 ACD 短，Dijkstra 会忘记 ACD 曾经是一种可能性（它使用 ACD 作为从 A 到 D 的规范路线）。但是如果 ABD 的成本高于 ACD，并且 ABDE 高于配额，而 ACDE 低于配额，那么现在消除的 ACD 是正确的。问题是 Dijkstra 的算法假设如果一条路径至少和另一条一样长，它是弱支配的：没有理由更喜欢它。在一个维度的比较中，路径是弱排序的：给定任意两条路径，一条弱支配另一条。

但是这里我们有两个比较维度，因此排序不成立：一个路径可以更短，另一个更便宜。由于我们只能丢弃支配路径，因此我们必须保留所有尚未超出预算且未被支配的路径。我在实施这种方法方面做了一些工作；它看起来可行，但找不到低于指数复杂度的最坏情况界限的论据（尽管正常性能应该要好得多，因为在理智的图中，大多数路径都占主导地位）。

正如 Billiska 所指出的，您还可以使用第 k 个最短路径算法，然后继续检查它们的结果，直到找到低于预算的路径。使用时间 O(m+ K*n*log(m/n)); 但是除非有人看到 K 的上限，这样 K 可以保证在预算范围内包含一条路径（如果存在），我们需要将 K 设置为路径的总数，再次产生指数复杂度（尽管策略又是至少在长度和成本合理相关的情况下，逐渐增加 K 可能会产生合理的平均运行时间）。

编辑：

使我提出的修改的实现复杂化（也许是致命的）是 Dijkstra 的算法依赖于节点可访问性的排序，因此我们知道，如果我们采用最短路径的未探索节点，我们将永远找不到更好的到它的路线（因为已知所有其他路线都更长）。如果那条最短的路线也很昂贵，那不必成立；即使在探索了一个节点之后，我们也必须准备好根据进入它的更长但更便宜的路径来更新离开它的路径。我怀疑这会阻止它在最坏的情况下达到多项式时间。

于 2012-11-21T03:41:31.597 回答
0

基本上你需要找到第一个最短路径，检查它是否有效，然后找到第二个最短路径，检查它是否有效，等等......

Dijkstra 的算法不适用于此类任务。只是在谷歌上搜索这个问题的新定义，我就找到了关于查找 kth-shortest-paths 的 Stack Overflow 问题。 我还没有读过，所以不要问我。我希望这有帮助。

于 2012-11-21T02:48:38.227 回答
0

我认为您可以使用 Dijkstra 来做到这一点，但是您必须更改在每一步中计算暂定距离的方式。不仅要考虑距离，还要考虑成本。新的距离应该是 2-d number (dist, cost)，当您选择最小距离时，您应该选择distAND最小的距离cost <= 6，就是这样。

我希望这是正确的。

于 2012-11-21T12:33:33.063 回答