Dijkstra 的负权重算法
Dijkstra's Algorithm for Negative Weights
好的，首先我知道 Dijkstra 不适用于负权重，我们可以使用 Bellman-ford 代替它。但是在一个问题中，我得到的是所有边的权重都在 0 到 1 之间（不包括 0 和 1）。而路径的成本其实就是乘积。
所以我想的只是拿日志。现在所有的边都是负的。现在我知道 Dijkstra 不适用于负权重，但在这种情况下，所有的边都是负的，所以我们不能做点什么让 Dijkstra 起作用。
虽然我想将所有权重乘以 -1，但是最短路径变成了最长路径。
那么在这种情况下我是否可以避免使用 Bellman-Ford 算法。
确切的问题是："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)."
如果图中所有的权重都在(0, 1)范围内，那么总会有一个权重小于1的循环，这样你就会卡在这个循环中曾经（循环中的每一次通过都会减少最短路径的总权重）。可能你误解了这个问题，你要么想找到最长的路径，要么不允许你访问同一个顶点两次。无论如何，在第一种情况下 dijkstra'a 算法是绝对适用的，即使没有 log 修改。而且我很确定第二种情况不能用多项式复杂度来解决。
您写道：
I though of multiplying all the weights by -1 but then the shortest
path becomes the longest path.
要在最短路径和最长路径之间切换，请反转权重。所以 1/3 将是 3，5 将是 1/5 等等。
所以您想使用一个函数，比方说 F，您将应用到原始图的权重，然后使用 Dijkstra 算法找到最短的乘积路径。我们还考虑下图，我们从节点 A 开始，其中 0 < x < y < 1:
在上图中，F(x) 必须小于 F(y)，Dijkstra 算法才能正确输出来自 A.
的最短路径
现在，让我们再次从节点 A:
开始，获取一个略有不同的图表
那么 Dijkstra 算法将如何工作？
既然F(x) < F(y)那么下一步我们将select节点B。然后我们将访问剩余的节点 C。 Dijkstra算法会输出从A到B的最短路径是A -> B，从A到C的最短路径是A -> C。
但是从 A 到 B 的最短路径是 A -> C -> B，成本 x * y < x。
这意味着我们无法找到权重转换函数并期望 Dijkstra 算法适用于所有情况。
如果你的图有循环，最短路径算法将找不到答案，因为这些循环总是 "negative cycles"，正如 Rontogiannis Aristofanis 指出的那样。
如果您的图表没有循环，您根本不必使用 Dijkstra。
如果是有向的，就是DAG，有线性时间最短路径算法。
如果它是无向的，它就是一棵树，在树中找到最短路径是微不足道的。如果你的图是有向的，即使没有循环，Dijkstra 仍然无法工作，原因与它不适用于负边图的原因相同。
在所有情况下，对于您的问题，Dijkstra 都是一个糟糕的算法选择。
好的，首先我知道 Dijkstra 不适用于负权重，我们可以使用 Bellman-ford 代替它。但是在一个问题中，我得到的是所有边的权重都在 0 到 1 之间（不包括 0 和 1）。而路径的成本其实就是乘积。
所以我想的只是拿日志。现在所有的边都是负的。现在我知道 Dijkstra 不适用于负权重，但在这种情况下，所有的边都是负的，所以我们不能做点什么让 Dijkstra 起作用。
虽然我想将所有权重乘以 -1，但是最短路径变成了最长路径。
那么在这种情况下我是否可以避免使用 Bellman-Ford 算法。
确切的问题是："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)."
如果图中所有的权重都在(0, 1)范围内，那么总会有一个权重小于1的循环，这样你就会卡在这个循环中曾经（循环中的每一次通过都会减少最短路径的总权重）。可能你误解了这个问题，你要么想找到最长的路径，要么不允许你访问同一个顶点两次。无论如何，在第一种情况下 dijkstra'a 算法是绝对适用的，即使没有 log 修改。而且我很确定第二种情况不能用多项式复杂度来解决。
您写道：
I though of multiplying all the weights by -1 but then the shortest path becomes the longest path.
要在最短路径和最长路径之间切换，请反转权重。所以 1/3 将是 3，5 将是 1/5 等等。
所以您想使用一个函数，比方说 F，您将应用到原始图的权重，然后使用 Dijkstra 算法找到最短的乘积路径。我们还考虑下图，我们从节点 A 开始，其中 0 < x < y < 1:
在上图中，F(x) 必须小于 F(y)，Dijkstra 算法才能正确输出来自 A.
现在，让我们再次从节点 A:
那么 Dijkstra 算法将如何工作？
既然F(x) < F(y)那么下一步我们将select节点B。然后我们将访问剩余的节点 C。 Dijkstra算法会输出从A到B的最短路径是A -> B，从A到C的最短路径是A -> C。
但是从 A 到 B 的最短路径是 A -> C -> B，成本 x * y < x。
这意味着我们无法找到权重转换函数并期望 Dijkstra 算法适用于所有情况。
如果你的图有循环，最短路径算法将找不到答案，因为这些循环总是 "negative cycles"，正如 Rontogiannis Aristofanis 指出的那样。
如果您的图表没有循环，您根本不必使用 Dijkstra。
如果是有向的，就是DAG，有线性时间最短路径算法。
如果它是无向的，它就是一棵树，在树中找到最短路径是微不足道的。如果你的图是有向的，即使没有循环，Dijkstra 仍然无法工作，原因与它不适用于负边图的原因相同。
在所有情况下，对于您的问题，Dijkstra 都是一个糟糕的算法选择。