好吧，首先我知道 Dijkstra 不适用于负权重，我们可以使用 Bellman-ford 代替它。但在我遇到的一个问题中，它指出所有边的权重都从 0 到 1（不包括 0 和 1）。而路径的成本实际上就是产品。
所以我的想法就是只取日志。现在所有的边都是负的。现在我知道 Dijkstra 不适用于负权重，但在这种情况下，所有边缘都是负的，所以我们不能做一些事情让 Dijkstra 起作用。
我想将所有权重乘以-1，但最短路径会变成最长路径。
那么在这种情况下我是否可以避免贝尔曼-福特算法呢？
确切的问题是：“假设对于某些应用，一条路径的成本等于该路径中所有边的权重的乘积。在这种情况下，您将如何使用 Dijkstra 算法？所有边的权重都从 0 开始到 1（不包括 0 和 1）。”
如果图表上的所有权重都在范围内(0, 1)，那么总会有一个循环的权重小于1，因此你将永远陷入这个循环（循环中的每一次传递都会减少最短路径的总重量）。可能你误解了这个问题，你要么想要找到最长的路径，要么不允许你两次访问同一个顶点。无论如何，在第一种情况下，dijkstra'a 算法绝对适用，即使没有log修改。我很确定第二种情况不能用多项式复杂度来解决。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
