Dijkstra的负权重算法
好吧，首先我知道迪克斯特拉不适合负重，我们可以用贝尔曼福特代替它。 但是在一个问题中，我给出了它的所有边都有从0到1的权重（0和1不包括在内）。 而路径的成本实际上就是产品。
所以我在想的是取日志。 现在所有的边缘都是负面的。 现在我知道迪克斯特拉不会为负面权重工作，但在这种情况下，所有的边缘都是负面的，所以我们不能做点什么来让迪克斯特拉工作。
我虽然把所有的权重乘以-1，但是最短的路径成为最长的路径。
因此，无论如何，我可以避免在这种情况下的Bellman-Ford算法。
确切的问题是：“假设对于某些应用，路径的成本等于产品路径中所有边的权重。在这种情况下，您将如何使用Dijkstra的算法？边的所有权重均为0到1（0和1不包括在内）“。
所以你想用一个函数，比如说F ，你将应用到原始图的权重，然后用Dijkstra的算法，你会发现最短的产品路径。 我们还考虑下面的图，我们从节点A开始，其中0 < x < y < 1 ：
在上面的图中，对于Dijkstra算法来说， F(x)必须小于F(y)才能正确输出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算法在任何情况下都能正常工作。
如果图上的所有权重都在(0, 1)的范围内，那么总是会有一个重量小于1的周期，因此您将永远停留在此周期中（每循环一次就会减少最短路径的总重量）。 可能你错误地理解了这个问题，你要么找到最长的路径，要么你不允许两次访问同一个顶点。 无论如何，在第一种情况下，即使没有log修改，dijkstra'a算法也是绝对适用的。 我很确定第二种情况不能用多项式复杂度来解决。
你写了：
我虽然把所有的权重乘以-1，但是最短的路径成为最长的路径。
在最短路径和最长路径之间切换权重。 所以1/3将是3 ， 5将1/5等。