Dijkstra算法处理负权重问题的方法

Question

Dijkstra算法处理负权重问题的方法

algorithmdijkstrashortest-path

7

首先我知道Dijkstra算法不能处理负权重，我们可以使用Bellman-Ford来代替它。但是在一个问题中，所有的边都有从0到1（不包括0和1）的权重，并且路径的成本实际上是乘积。

因此，我想的方法是将其取对数。现在所有的边都是负的。我知道Dijkstra算法不能处理负权重，但在这种情况下所有的边都是负的，所以我们不能做一些事情让Dijkstra能够处理吗？

我想过将所有的权重乘以-1，但最短路径会变成最长路径。

那么在这种情况下，有没有办法避免使用Bellman-Ford算法呢？

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

- S. Salman

2

首先，我假设图是有向的。如果权重在0和1之间，并且成本由权重的乘积衡量，则确实正在寻找最长路径。如果图中存在任何循环，则等同于负成本循环。 - Abhishek Bansal

所以Dijkstra算法可以使用。我只需要找到最长的路径。另外，没有给出任何其他要求，这就是我感到困惑的原因。 - S. Salman

你确定不想要最有可能的路径吗？ - David Eisenstat

我已经给了你确切的问题，请阅读最后三行。 - S. Salman

是的，我在发表评论时已经阅读了那些代码行。有些人非常准确地要求他们并没有意识到自己并不需要的东西。 - David Eisenstat

4个回答

1

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

Second graph

在上面的图中，对于Dijkstra算法正确输出从节点A到最短路径，F(x)必须小于F(y)。

现在，让我们看一个略微不同的图，我们从节点A重新开始：

First graph

那么Dijkstra算法如何工作呢？

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

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

这意味着我们不能找到一个权重变换函数并期望Dijkstra算法在每种情况下都能正常工作。

- JuniorCompressor

0

如果你的图有环，任何最短路径算法都无法找到答案，因为这些环总是“负环”，正如Rontogiannis Aristofanis所指出的那样。

如果你的图没有环，你根本不需要使用Dijkstra算法。

如果它是有向图，则是一个DAG，有线性时间的最短路径算法。

如果它是无向图，则是一棵树，在树中找到最短路径很容易。如果你的图是有向的，即使没有环，Dijkstra仍然不能工作，原因与负边缘图相同。

在所有情况下，Dijkstra算法都是解决你的问题的可怕选择。

- Juan Lopes

0

你写道：

我曾考虑将所有权重乘以-1，但这样最短路径就会变成最长路径。

要在最短路径和最长路径之间切换，请反转权重。因此，1/3 将变为 3，5 将变为 1/5 等等。

- Zsolt Mester

但是如果你取反，它将不再给出相同的答案。假设你有dist(a,c)=1，dist(a,b)=2，dist(b,c)=2。最长路径是a-b-c成本为4。如果你取反，我们有dist(a,c)=1，dist(a,b)=0.5，dist(b,c)=0.5。这里a-b-c和a-c都有相同的最短路径。 - justhalf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rontogiannis Aristofanis · Accepted Answer

如果图中所有的权重都在范围 (0, 1) 内，那么总会存在一个权重小于 1 的循环，这将导致你永远陷入这个循环中（每次通过循环都会减少最短路径的总权重）。也许你误解了问题，你可能想找到最长的路径，或者不允许多次访问同一个顶点。无论哪种情况，第一种情况下 Dijkstra 算法肯定适用，甚至不需要进行 log 修改。而我非常确定第二种情况不能以多项式复杂度解决。