为什么Dijkstra算法不适用于负权重边缘？
有人可以告诉我为什么Dijkstra的单源最短路径算法假定边缘必须是非负的。
我只谈论的不是负面的重量周期。
回想一下，在Dijkstra的算法中， 一旦顶点被标记为“闭合”（并且不在开放集合中），该算法找到了它的最短路径 ，并且将不再需要再次开发该节点 - 它假设为此开发的路径路径是最短的。
但负面的权重 - 可能并非如此。 例如：
A
/
/
/
5 2
/
B--(-10)-->C
V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}
A的Dijkstra将首先开发C，并且稍后将无法找到A->B->C
编辑更深入的解释：
请注意，这很重要，因为在每个松弛步骤中，算法假定“关闭”节点的“成本”确实是最小的，因此接下来将选择的节点也是最小的。
它的想法是：如果我们有一个开放的顶点，使其成本最小 - 通过向任何顶点添加任何正数 - 最小值永远不会改变。
没有正数的限制 - 上述假设是不正确的。
由于我们“知道”每个“关闭”的顶点是最小的 - 我们可以安全地进行松弛步骤 - 无需“回顾”。 如果我们确实需要“回顾” - Bellman-Ford提供了一个类似递归的（DP）解决方案。
考虑下面显示的图形，源代码为顶点A.首先尝试自己运行Dijkstra的算法。
当我在我的解释中提到Dijkstra的算法时，我将讨论下面实现的Dijkstra算法，
因此，开始分配给每个顶点的值 （从源到顶点的距离）
我们首先提取具有最小值的Q = [A，B，C]中的顶点，即A，之后Q = [B，C] 。 注意A对B和C有一个有向边，它们都在Q中，因此我们更新这两个值，
现在我们将C提取为（2 <5），现在Q = [B] 。 请注意C没有连接，所以line16循环不运行。
最后我们提取B，之后 。 注意B有向边至C，但C是不存在Q中，因此我们再次没有进入中环路line16 ，
所以我们最终的距离为
请注意，这是错误的，因为当你离开A到C的最短距离是5 + -10 = -5时 。
所以对于这个图，Dijkstra算法错误地计算了从A到C的距离
发生这种情况是因为Dijkstra算法不会尝试找到已经从Q中提取的顶点的较短路径。
line16循环正在做的是取顶点u并且说：“嘿看起来我们可以通过u从源头去v ，那么距离我们得到的当前dist [v]有多远？更新dist [v] “
请注意，在line16他们检查所有邻居V（即从u存在到v的有向边），U的它仍然在Q值 。 在第line14他们从Q中删除已访问的笔记。因此，如果x是u的访问邻居，路径 甚至不被认为是从源到v可能更短的方式。
如果边权重都是正数，这实际上很有用，因为那样我们就不会浪费时间考虑不能缩短的路径。
所以我说当运行这个算法时，如果x在y之前从Q中提取，那么它不可能找到一个路径 - 这比较短。 让我用一个例子来解释这一点，
由于y刚刚被提取，并且x已经被提取出来，所以dist [y]> dist [x] ，否则y将在x之前被提取。 （先行line 13分钟的距离）
因为我们已经假定边权重是正的，即长度（x，y）> 0 。 所以通过y的替代距离（alt）总是肯定会更大，即dist [y] + length（x，y）> dist [x] 。 因此，即使y被认为是x的路径， dist [x]的值也不会被更新，因此我们得出结论认为只考虑y中仍然存在的y的邻居是有意义的（注意在第line16注释）
但是这个东西取决于我们假设的正边长度，如果长度（u，v）<0，那么取决于边缘的负值是多少，我们可以用line18的比较后的dist [x]来line18 。
因此，如果x在所有顶点v之前被移除（使得x是v的邻居并且负边缘连接它们），我们所做的任何dist [x]计算都将不正确。
因为这些v个顶点中的每一个都是从源到x的潜在“更好”路径上的第二个最后一个顶点，这被Dijkstra算法丢弃。
所以在上面给出的例子中，错误是因为在B被移除之前C被移除了。 虽然那个C是B的一个邻居，但有一个负面的优势！
为了澄清，B和C是A的邻居。 B有一个单独的邻居C，C没有邻居。 长度（a，b）是顶点a和b之间的边长。
Dijkstra的算法假定路径只能变得“更重”，所以如果你有一条从A到B的路径，权重为3，路径从A到C的权重为3，那么你就没有办法添加边缘和从A到B通过C，重量小于3。
这个假设使算法比必须考虑负值的算法更快。
链接地址: http://www.djcxy.com/p/6005.html上一篇: Why doesn't Dijkstra's algorithm work for negative weight edges?