Dijkstra的负权重算法

Question

好的,首先我知道Dijkstra不适用于负重量,我们可以使用Bellman-ford代替它.但是在一个问题中,我给它说明所有边都有从0到1的权重(不包括0和1).而路径的成本实际上就是产品.

所以我在想的只是记录日志.现在所有的边都是负的.现在我知道Dijkstra不会用于负权重,但在这种情况下所有边缘都是负数,所以我们不能做一些事情让Dijkstra工作.

我将所有权重乘以-1,但最短路径成为最长路径.

那么无论如何我可以在这种情况下避免使用Bellman-Ford算法.

确切的问题是:"假设对于某些应用,路径的成本等于路径中边缘的所有权重.在这种情况下你将如何使用Dijkstra算法？边缘的所有权重都是0为1(0和1不包括在内)."

Answer 1

因此，您想要使用一个函数，比方说F，您将应用到原始图的权重，然后使用 Dijkstra 算法，您将找到最短的乘积路径。我们还考虑以下从节点A和开始的图0 < x < y < 1：

上图中F(x)必须小于F(y)Dijkstra 算法才能正确输出 的最短路径A。

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

那么 Dijkstra 算法是如何工作的呢？

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

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

这意味着我们无法找到权重变换函数并期望 Dijkstra 算法在每种情况下都有效。