Dijkstra负权数算法 [英] Dijkstra's Algorithm for Negative Weights

问题描述

好吧，首先，我知道Dijkstra不适用于负重，我们可以用Bellman-ford代替它。但是在一个问题中，我被告知所有边缘的权重为0到1（不包括0和1）。路径的成本实际上就是产品。

所以我在想的只是记录日志。现在所有的边缘都是负的。现在我知道Dijkstra不会对负权重起作用，但是在这种情况下，所有边缘都是负值，所以我们不能做些什么让Dijkstra起作用。

我虽然将所有权重乘以-1，然后最短路径变为最长路径。

所以在这种情况下，我仍然可以避免使用Bellman-Ford算法。 / p>

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

解决方案

因此，您想使用一个函数，例如 F ，您将其应用于原始图形的权重，然后使用Dijkstra的算法，您将找到最短的产品路径。让我们考虑下图，我们从节点 A 开始，其中 0< x ＜ & 1 ：

在上图中， F（x）必须小于 F（ y）来使Dijkstra的算法正确输出 A 的最短路径。

现在，让我们做一个稍微不同的图，我们再次从节点 A 开始：

那么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的算法在每种情况下都能工作。

Okay, first of all I know Dijkstra does not work for negative weights and we can use Bellman-ford instead of it. But in a problem I was given it states that all the edges have weights from 0 to 1 (0 and 1 are not included). And the cost of the path is actually the product.

So what I was thinking is just take the log. Now all the edges are negative. Now I know Dijkstra won't work for negative weights but in this case all the edges are negative so can't we do something so that Dijkstra would work.

I though of multiplying all the weights by -1 but then the shortest path becomes the longest path.

So is there anyway I can avoid the Bellman-Ford algorithm in this case.

The exact question is: "Suppose for some application, the cost of a path is equal to the product all the weights of the edges in the path. How would you use Dijkstra's algorithm in this case? All the weights of the edges are from 0 to 1 (0 and 1 are not inclusive)."

解决方案

So you want to use a function, let's say F, that you will apply to the weights of the original graph and then with Dijkstra's algorithm you'll find the shortest product path. Let's also consider the following graph that we start from node A and where 0 < x < y < 1:

In the above graph F(x) must be smaller than F(y) for Dijkstra's algorithm to output correctly the shortest paths from A.

Now, let's take a slightly different graph that we start again from node A:

Then how Dijkstra's algorithm will work?

Since F(x) < F(y) then we will select node B at the next step. Then we'll visit the remaining node C. Dijkstra's algorithm will output that the shortest path from A to B is A -> B and the shortest path from A to C is A -> C.

But the shortest path from A to B is A -> C -> B with cost x * y < x.

This means we can't find a weight transformation function and expect Dijkstra's algorithm to work in every case.

这篇关于Dijkstra负权数算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！