为什么Dijkstraalgorithm不适用于负权重边缘？
有人可以告诉我为什么Dijkstra的单源最短pathalgorithm假定边缘必须是非负的。
我只谈论的不是负面的重量周期。
回想一下，在Dijkstra的algorithm中， 一旦顶点被标记为“closures”（并且不在开放集合中），该algorithmfind了最短path ，并且将永远不必再次开发该节点 – 它假定为此开发的pathpath是最短的。
但负面的权重 – 这可能不是真的。 例如：
A / \ / \ / \ 5 2 / \ B--(-10)-->C V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)} A的Dijkstra将首先开发C，稍后将无法findA->B->C
编辑一下更深入的解释：
请注意这一点很重要，因为在每个松弛步骤中，algorithm假设“closures”节点的“成本”确实是最小的，因此接下来要select的节点也是最小的。
它的想法是：如果我们有一个开放的顶点，使得它的代价是最小的 – 通过给任何顶点添加任何正数 – 最小值永远不会改变。
没有正数的约束 – 上面的假设是不正确的。
既然我们知道每一个“closures”的顶点都是最小的，我们就可以安全地进行松弛步骤，而不用“回头看”。 如果我们需要“回顾”， Bellman-Ford提供了一个类似recursion的（DP）解决scheme。
考虑下图所示的graphics，源代码为顶点A.首先尝试运行Dijkstra的algorithm。
当我在我的解释中提到Dijkstraalgorithm时，我将会讨论下面实现的Dijkstraalgorithm，
因此，开始分配给每个顶点的值 （ 从源到顶点的距离 ）
我们首先提取具有最小值的Q = [A，B，C]中的顶点，即A，之后Q = [B，C] 。 注意A对B和C有一个有向边，它们也都在Q中，因此我们更新这两个值，
现在我们提取C（2 <5），现在Q = [B] 。 请注意，C没有连接，所以line16循环不运行。
最后我们提取B，之后 
。 注意B对C有一个有向边，但C不存在于Q中，因此我们再次不在16行inputfor循环，
所以我们最终的距离为
请注意，这是错误的，因为从A到C的最短距离是5 + -10 = -5 
。
所以对于这个图，Dijkstraalgorithm错误地计算了从A到C的距离
发生这种情况是因为Dijkstraalgorithm不会尝试find已经从Q中提取的顶点的较短path。
line16循环所做的就是取顶点u并说： “嘿，看起来我们可以通过u从源头去v ，那么比我们得到的当前dist [v]更好吗？更新dist [v] “
请注意，在第line16他们检查所有仍在Q中的邻居v （即从u到v存在的有向边）。 在第line14他们从Q中删除了访问过的笔记。所以如果x是u的访问邻居，path 
甚至不被视为从源到v可能更短的方式。
如果边权重都是正数 ，这实际上是有用的 ，因为那样我们就不会浪费时间考虑不能缩短的path。
所以我说当运行这个algorithm时，如果x是从y之前的Q中提取的，那么它不可能find一个path – 
这是更短的。 我来举个例子来解释一下，
由于y刚刚被提取，并且x已经被提取，所以dist [y]> dist [x] ，否则y将在x之前被提取。 （第一line 13分钟）
而且我们已经假定边权重是正的，即长度（x，y）> 0 。 所以通过y的替代距离（alt）总是肯定会更大，即dist [y] + length（x，y）> dist [x] 。 因此，即使y被认为是到x的path， dist [x]的值也不会被更新，因此我们得出结论认为只考虑y中仍然存在的y的邻居是有意义的（注意在第line16 ）
但是这个东西取决于我们假设的正边长度，如果长度（u，v）<0，那么取决于边缘的负值是多less，我们可以用line18的比较来replacedist [x] 。
因此，如果x在所有顶点v之前被移除，那么任何dist [x]计算都是不正确的，因此x是v的邻居，负边连接它们 – 被移除。
因为这些v个顶点中的每一个都是从源到x的潜在“更好”path上的第二个最后一个顶点，这被Dijkstraalgorithm丢弃了。
所以在上面给出的例子中，错误是因为C在B被移除之前被移除了。 虽然那个C是一个负面的边缘B的邻居！
为了澄清，B和C是A的邻居。 B有一个单一的邻居C和C没有邻居。 长度（a，b）是顶点a和b之间的边长。
Dijkstra的algorithm假设path只能变得更“重”，所以如果你有一条从A到B的path，权重为3，path从A到C的权重为3，那么你就不可能添加一条边从A到B通过C，重量小于3。
这个假设使得algorithm比必须考虑负的权重的algorithm更快。
Dijkstraalgorithm的正确性：
algorithm的每一步我们有2组顶点。 集合A由我们已经计算最短path的顶点组成。 集合B由剩下的顶点组成。
归纳假设 ：在每一步我们将假设所有以前的迭代是正确的。
归纳步骤 ：当我们将一个顶点V添加到集合A并将距离设置为dist [V]时，我们必须certificate这个距离是最优的。 如果这不是最佳的，那么必须有一些其他path到较短长度的顶点V.
假设这个path经过某个顶点X.
现在，因为dist [V] <= dist [X]，所以除非graphics具有负边长度，否则到V的任何其他path将是至lessdist [V]长度。
因此，为了dijkstraalgorithm的工作，边权重必须是非负的。
假设A是源节点，试试下图Dijkstra的algorithm，看看发生了什么：
