问Dijkstra算法与负权与循环

EN

迪克斯特拉算法只适用于具有非负边的图.这是因为它假设当一个节点第一次从队列中弹出时，我们已经找到了到达该节点的最短路径，而且即使有一个负重，这也不一定是正确的。

因此I是假的，II是假的(因为负循环未必是可达的)，III是真，IV是假的(即使没有负循环，它仍然有负的边)。

如果我没记错的话，Dijkstra的算法(至少是经典版本)有一个内置的假设，即图中的所有权重都是非负的。因此，如果我们在图中有负边，我们就不能保证它能正确工作。

(1)在第一种情况下，我们最有可能得到一条最长的边链，其权重绝对值最高作为最短路径，从技术上讲，这是正确的最短路径。(我假设这个图没有负圈)

( II)误为负循环可能是不可达的(如Peter de Rivaz 正确地说)

我假设第三段是关于有负权的边的图，但没有负循环。在这种情况下，有可能在一个循环中嵌入算法，因为它可以找到一个具有负权边的循环，在算法中的某个点上，我们决定了一个边的权重的下一步。毫无疑问，消极的循环永远是第一选择，所以即使有一个非负的循环，我们也有无限循环的可能性。