Dijkstra 算法与负权重和循环
Dijkstra's Algorithms and Negative Weights and Cycle
我在研究贪心算法。总结有关 Dijkstra 算法的一些重要方面，这将是正确的。我怀疑 (4) 和 (1)，有人可以帮助我吗？
I) 如果所有边的权重都是负数，Dijkstra 算法运行良好。
II) 如果在图中我们有一个负循环，Dijkstra 会进入一个无限循环并且永远不会结束。
III) 如果一个图只有负权重的单边，但没有负环，则该算法效果不佳。
IV) 如果图没有负循环，则算法运行良好。
Dijkstra's algorithm 仅适用于具有非负边的图。这是因为它假设第一次从队列中弹出一个节点时，我们已经找到了到该节点的最短路径，而即使您有一个负权重，这也不一定是正确的。
因此I为假，II为假（因为负循环不一定可达），III为真，IV为假（即使没有负循环也可能还有负边）
如果我没记错的话，Dijkstra 的算法（至少是它的经典版本）有一个内置的假设，即图中的所有权重都是非负的。因此，如果我们的图中有负边，我们无法保证它会正常工作。
I) 在第一种情况下，我们很可能会得到最长的可能边链，其中权重的绝对值最高作为最短路径，从技术上讲，这将是正确的最短路径。 （我假设图表没有负循环）
II) 错误，因为可能无法到达负循环（如 Peter de Rivaz ）
III-IV) 我假设第 3 段是关于图的一条边为负 weight，但没有负循环。在这种情况下，算法有可能陷入循环，因为它可以找到一个带有负权重边的循环，这对算法来说似乎是一个很好的路径延长，因为在算法的某个时刻我们决定下一步一条边的权重。毫无疑问，负数永远是第一选择，所以即使是非负循环，我们也有无限循环的可能性。
我在研究贪心算法。总结有关 Dijkstra 算法的一些重要方面，这将是正确的。我怀疑 (4) 和 (1)，有人可以帮助我吗？
I) 如果所有边的权重都是负数，Dijkstra 算法运行良好。
II) 如果在图中我们有一个负循环，Dijkstra 会进入一个无限循环并且永远不会结束。
III) 如果一个图只有负权重的单边，但没有负环，则该算法效果不佳。
IV) 如果图没有负循环，则算法运行良好。
Dijkstra's algorithm 仅适用于具有非负边的图。这是因为它假设第一次从队列中弹出一个节点时，我们已经找到了到该节点的最短路径，而即使您有一个负权重，这也不一定是正确的。
因此I为假，II为假（因为负循环不一定可达），III为真，IV为假（即使没有负循环也可能还有负边）
如果我没记错的话，Dijkstra 的算法（至少是它的经典版本）有一个内置的假设，即图中的所有权重都是非负的。因此，如果我们的图中有负边，我们无法保证它会正常工作。
I) 在第一种情况下，我们很可能会得到最长的可能边链，其中权重的绝对值最高作为最短路径，从技术上讲，这将是正确的最短路径。 （我假设图表没有负循环）
II) 错误，因为可能无法到达负循环（如 Peter de Rivaz
III-IV) 我假设第 3 段是关于图的一条边为负 weight，但没有负循环。在这种情况下，算法有可能陷入循环，因为它可以找到一个带有负权重边的循环，这对算法来说似乎是一个很好的路径延长，因为在算法的某个时刻我们决定下一步一条边的权重。毫无疑问，负数永远是第一选择，所以即使是非负循环，我们也有无限循环的可能性。