algorithm - Dijkstra 算法与负权重和循环

Question

我研究贪心算法。总结有关 Dijkstra 算法的一些重要方面，这将是正确的。我怀疑 (4) 和 (1)，有人可以帮助我吗？

I) 如果所有边的权重都是负数，则 Dijkstra 算法运行良好。

II) 如果在图中我们有一个负循环，Dijkstra 会进入一个无限循环并且永远不会结束。

III)如果一个图有一条负权重的边，但没有负环，则该算法效果不佳。

IV) 如果图没有负循环，则算法运行良好。

Answer 1

Dijkstra's algorithm仅适用于具有非负边的图。这是因为它假设第一次从队列中弹出一个节点时，我们已经找到了到该节点的最短路径，而即使您有一个负权重，这也不一定是正确的。

因此I为假，II为假(因为负循环不一定可达)，III为真，IV为假(即使没有负循环也可能还有负边)