Dijkstra的算法和负权重和周期
我研究贪婪算法。 总结Dijkstra算法的一些重要方面，这将是真实的。 我怀疑（4）和（1），任何人都可以帮助我？
I）如果所有边的权重都是负的，那么Dijkstra算法运行良好。
II）如果在图中我们有一个负循环，Dijkstra进入一个无限循环并且永不结束。
III）如果一个图具有一个负权重的边，但没有负周期，则该算法效果不佳。
IV）如果图形没有负循环，算法运行良好。
Dijkstra算法仅适用于具有非负边的图。 这是因为它假设第一次从队列中弹出一个节点时，我们找到了到达该节点的最短路径，并且只要有一个负权重，这就不一定是真的。
因此，我是错误的，II是错误的（因为负循环可能不一定可达），III是真实的，IV是错误的（即使没有负循环，它仍然有负边缘）。
如果我记得正确的话，Dijkstra的算法（至少是它的经典版本）有一个内置的假设，即图中的所有权重都是非负的。 所以我们不能保证，如果我们的图中有负边，它将正常工作。
I）在第一种情况下，我们很可能会获得最长的可能链条，其权重绝对值最高为最短路径，从技术上讲，这将是正确的最短路径。 （我假设图表没有负循环）
II）假阴性循环可能无法达到（正如Peter de Rivaz所说的）
III-IV）我假定第3段是关于具有负重量的一个边的图，但是没有负循环。 在这种情况下，在循环中有算法卡住的可能性，因为它可以找到一个具有负加权边的循环，这对算法来说似乎是一个好的路径延长，因为在我们决定下一步的算法的某个点一个边的重量。 负面的一个将永远是第一选择毫无疑问，所以即使有一个非负循环，我们有可能无限循环。
链接地址: http://www.djcxy.com/p/35245.html