这是我的问题的可视化展示：
我一直在尝试使用Djikstra算法解决它，但是还没有成功。
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算法的实现变得更加复杂（也许是致命的），因为它依赖于节点可访问性的排序，这样我们就知道如果我们采取最短路径到未探索的节点，我们永远不会找到更好的路线（因为已知所有其他路线都比它长）。如果最短路径也很昂贵，那么这种情况可能不成立；即使在探索节点之后，我们也必须准备根据更长但更便宜的路径更新出它的路径。我怀疑这将阻止它在最坏情况下达到多项式时间。
- isturdy
2
我期望算法能够找到第k短路径，并且能够重复使用找到(k-1)短路径的结果。因此，希望时间复杂度不会像你所说的那样是
O(m+ K*n*log(m/n))。 - Apiwat Chantawibul这个限制是直接从http://www.springerlink.com/content/pl0054nt2d0d2u3t/得来的。但是，即使我们可以在常数时间内找到新的第K短路径（不可能乐观），我们仍然有O(m+n log n + K)，除非我们能够找到需要分析的最大K的多项式界限，否则仍然是指数级的。 - isturdy
0
基本上，您需要找到第一条最短路径，检查它是否有效，然后找到第二条最短路径，检查它是否有效，以此类推...
Dijkstra算法并不适用于这种任务。 通过在Google上搜索这个问题的新定义， 我找到了Stack Overflow关于查找第k短路径的问题。 我还没有深入研究它，所以别问我。 希望这可以帮到您。
- Apiwat Chantawibul
0
我认为你可以用Dijkstra算法来实现，但是你需要改变每一步中计算临时距离的方式。除了考虑距离之外，还要考虑成本。新的距离应该是一个二维数值 (dist, cost)，当你选择最小距离时，应该选择满足 dist 最小且 cost <= 6 的那个。
希望这样解释正确无误。
- zenpoy
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
{5,6}，而不是{4,6}...当然这并不会改变解决方案，但还是要注意。 - twalberg