Dijkstra的负重算法

好的，首先我知道Dijkstra不适用于负重，我们可以使用Bellman-ford来代替它。但是在一个问题中，我给出了它的所有边都有从0到1的权重（0和1不包括在内）。而路径的成本实际上就是产品。Dijkstra的负重算法

所以我在想的就是取日志。现在所有的边缘都是负面的。现在我知道迪克斯特拉不会为负面权重工作，但在这种情况下，所有的边缘都是负面的，所以我们不能做点什么来让迪克斯特拉工作。

我虽然所有的权重乘以-1，但最短的路径成为最长的路径。

因此，无论如何，我可以避免在这种情况下的贝尔曼 - 福特算法。

确切的问题是：“假设对于某些应用，路径的成本等于路径中所有边的权重乘积。在这种情况下，您将如何使用Dijkstra算法？所有权重边缘从0到1（0和1不包括在内）“。

来源

2015-04-18 George J. Adams

首先，我假设图是指向的。现在，如果权重在0到1之间，并且成本是通过权重的乘积来衡量的，那么您的确在寻找最长的路径。如果图中有任何周期，那么它相当于一个负成本周期。 –

因此Dijkstra会工作。我只需要找到最长的路径。另外，没有额外的要求，因此我很困惑。 –

你确定你不想要最可能的路径吗？ –

所以，你想用一个函数，比如说F，你将应用于原始图的权重，然后用Dijkstra的算法找到最短的产品路径。我们还要考虑以下图中，我们从节点A开始，其中0 < x < y < 1：

Second graph

在上图中F(x)必须比F(y)较小的Dijkstra算法正确输出的最短路径从A。

现在，让我们来稍微不同的曲线图，我们从节点A重新开始：

First graph

然后Dijkstra算法是如何工作的？

由于F(x) < F(y)那么我们将在下一步选择节点B。然后我们将访问剩余的节点C。Dijkstra算法将输出从A到B的最短路径是A -> B从A到C的最短路径是A -> C。

但是从A到B的最短路径是A -> C -> B，成本x * y < x。

这意味着我们无法找到一个重量转换功能，并期望Dijkstra算法，以在任何情况下工作。

来源

2015-04-18 11:02:18 JuniorCompressor

如果图表上的所有权重都在(0, 1)范围内，那么总会有一个重量小于1的周期，因此您将永远停留在此周期中（每循环一次就会减少最短路径的总重量）。可能你错误地理解了这个问题，你要么找到最长的路径，要么你不允许两次访问同一个顶点。无论如何，在第一种情况下，即使没有log修改，dijkstra'a算法也是绝对适用的。我很确定第二种情况不能用多项式复杂度来解决。

来源

2015-04-18 09:52:41

如果我们不允许两次访问同一个顶点，该怎么办？ –

@GeorgeAdams这是我在回答中提到的第二个案例。你可以减少你的问题找到最长的路径，因此没有已知的多项式解决方案（查看本文：http://cstheory.stackexchange.com/questions/17462/finding-the-shortest-path-in-the - 负循环的呈现） –

完美答案。 Just nit picking：你可以减少找到最长的路径，这就是证明NP硬度。 –

您写道：

我虽然-1所有的权重，但随后的最短路径成为最长路径相乘。

要在最短路径和最长路径之间切换权重。所以1/3将是3,5将是1/5等。

来源

2015-04-18 10:36:47

但是，如果你反过来，它不会再给出同样的答案。假设你有dist（a，c）= 1，dist（a，b）= 2，dist（b，c）= 2。最长的路径是a-b-c cost 4.如果反过来，我们有dist（a，c）= 1，dist（a，b）= 0.5，dist（b，c）= 0.5。这里a-b-c和a-c具有相同的最短路径。 – justhalf

如果你的图有个周期，没有最短路径算法会找到答案，因为这些周期将永远是“负循环”，作为Rontogiannis Aristofanis指出。

如果你的图表没有周期，你不必使用Dijkstra的所有。

如果它被引导，这是一个DAG和有线性时间最短路径算法。

如果是无向，这是一棵树，是微不足道的发现在树上的最短路径。如果你的图是直接的，即使没有循环，Dijkstra仍然不会工作，因为它不适用于负边缘图。

在所有情况下，Dijkstra算法是算法为您的问题一个可怕的选择。

来源

2015-04-24 02:35:13

Dijkstra的负重算法

回答

相关问题