查找成本最低的快速路径，小于或等于指定的

这是我的问题的可视化。查找成本最低的快速路径，小于或等于指定的

enter image description here

我一直在试图上但是，没有工作使用djikstra。

来源

2012-11-20 Patryk

[你有什么尝试？]（http://mattgemmell.com/2008/12/08/what-have-you-tried/） – alestanis

对我来说第一种可能性，应该是'{5,6 }'，而不是'{4,6}'......当然不会改变解决方案，但仍然... – twalberg

你看过加权图表上的材料吗？这听起来像是最小成本生成树和最短路径放在一起。 –

基本上你需要找到第一最短路径，检查是否正常工作，然后找第二最短路径，检查是否正常工作，等等...

Dijkstra算法的目的不是要与这样的任务合作。而只是谷歌搜索这个问题的新定义，我到达Stack Overflow question on finding kth-shortest-paths. 我还没有读到它，所以不要问我。我希望这可以帮助。

来源

2012-11-21 02:48:38 Billiska

并发症的发生，在我看来，是，Dijkstra算法扔掉，你需要保持周围的信息：如果你想从A点到E在

B 
/ \ 
A  D - E 
\ /
    C

和Abd比ACD短，迪克斯特拉会忘记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-21 03:41:31 isturdy

那么，我期望算法找到第k个最短路径，以便能够重用查找结果（k-1 ）TH-最短路径。所以希望时间复杂度不会像你说的那样是'O（m + K * n * log（m/n））'。 – Billiska

从http://www.springerlink.com/content/pl0054nt2d0d2u3t/直接获得。但是，即使我们能够在常量时间内找到新的第K个最短路径（不可能是乐观的），我们仍然有O（m + n log n + K），它仍然是指数的，除非我们能够找到一个多项式，分析。 – isturdy

我认为你可以用Dijkstra做到这一点，但是你必须改变你在每一步中计算试探距离的方式。不要只考虑距离，还要考虑成本。新的距离应该是2-d数字(dist, cost)，当你选择什么是最小距离，你应该采取最小dist和cost <= 6，就是这样。

我希望这是正确的。

来源

2012-11-21 12:33:33 zenpoy

查找成本最低的快速路径，小于或等于指定的

回答

相关问题