使用Dijkstraalgorithm的负权重
我想了解为什么Dijkstraalgorithm不能用负权重。 阅读最短path示例，我试图找出以下情况：
2 A-------B \ / 3 \ / -2 \ / C 从网站：
如果我们从A开始，那么Dijkstra的algorithm将select最小化d（A，A）+长度（边）的边（A，x），即（A，B）。 然后设d（A，B）= 2并select另一个边（y，C），使d（A，y）+ d（y，C）最小。 唯一的select是（A，C），它设置d（A，C）= 3。 但它从来没有find从A到B的最短path，通过C，总长度为1。
我不明白为什么使用下面的Dijkstra的实现，d [B]不会更新到1 （当algorithm到达顶点C时，它将在B上运行放松，看到d [B]等于2 ，并且因此将其值更新为1 ）。
Dijkstra(G, w, s) { Initialize-Single-Source(G, s) S ← Ø Q ← V[G]//priority queue by d[v] while Q ≠ Ø do u ← Extract-Min(Q) S ← SU {u} for each vertex v in Adj[u] do Relax(u, v) } Initialize-Single-Source(G, s) { for each vertex v V(G) d[v] ← ∞ π[v] ← NIL d[s] ← 0 } Relax(u, v) { //update only if we found a strictly shortest path if d[v] > d[u] + w(u,v) d[v] ← d[u] + w(u,v) π[v] ← u Update(Q, v) }
谢谢，
梅厄
你所build议的algorithm确实会在这个图中find最短path，但并不是所有的图都是一般的。 例如，考虑这个图表：
假设边缘是从左到右，如你的例子，
你的algorithm将如下工作：
- 首先，将
d(A)设置zero，其他距离设置为infinity。 - 然后展开节点
A，将d(B)设置为1，将d(C)设置zero，将d(D)为99。 - 接下来，你展开
C，没有净变化。 - 然后，你扩大了
B，这是没有效果的。 - 最后，展开
D，它将d(B)更改为-201。
注意，尽pipe到C的最短path长度为-200 ，但d(C)仍然为0 。 因此，在某些情况下，您的algorithm无法准确计算距离。 而且，即使你要存储返回指针，说明如何从每个节点到开始节点A ，你也会结束从C到A的错误path。
请注意，如果图表没有负循环，即加权总和小于零的循环，那么Dijkstra即使对于负权重也是有效的。
当然，有人可能会问，为什么在templatetypedef的例子中，即使没有负循环，Dijkstra也会失败，事实上甚至不是循环。 这是因为他正在使用另一个停止标准，一旦到达目标节点（或者所有节点已经被解决一次，他没有确切地指定）就保存该algorithm。 在没有负重的图表中，这可以正常工作。
如果使用替代停止标准，当优先级队列（堆）运行空闲时停止algorithm（这个停止标准也用于问题中），那么dijkstra即使对于具有负权重的图也能find正确的距离负循环。
然而，在这种情况下，没有负循环的图的dijkstra的渐近时间范围是丢失的。 这是因为当由于负权重而发现更好的距离时，先前定居的节点可以被重新插入到堆中。 这个属性被称为标签更正。
你没有在algorithm的任何地方使用S（除了修改它）。 dijkstra的概念曾经是一个顶点在S上，它不会再被修改。 在这种情况下，一旦B在S内部，你将不会再通过C.
这个事实确保了O（E + VlogV）的复杂性[否则，你将会重复多次一次的边，并且多于一次的顶点]
换句话说，您发布的algorithm可能不在O（E + VlogV）中，正如dijkstra的algorithm所承诺的那样。
由于Dijkstra是一个贪婪的方法，一旦一个顶点被标记为这个循环的访问，即使有另外一条path以较低的成本到达，它也不会再被重新评估。 而这样的问题只有在图中存在负边时才会发生。
一个贪婪的algorithm ，顾名思义， 总是让这个select似乎是当时最好的。 假设你有一个目标函数需要在给定的点上进行优化（最大化或最小化）。 贪婪algorithm在每一步都会进行贪婪的select，以确保目标函数得到优化。 贪婪algorithm只有一个镜头来计算最佳解决scheme，以便它永远不会倒退，并决定。
考虑一下如果你在B和C之间来回发生什么事，那么瞧吧
（只有在图表没有被引导时才相关）
编辑：我认为这个问题与AC *的path只有在负权重边缘存在的情况下才会比AB好，因此，在AC之后去哪里并不重要，一旦你select去AC之后到达B，那么就不可能find比AB更好的path。
“2）我们可以使用Dijksra的algorithm为具有负权的图的最短path – 一个想法可以是，计算最小权重值，向所有权重添加正值（等于最小权重值的绝对值）并运行Dijksraalgorithm对于修改后的图，这个algorithm会起作用吗？
除非所有最短path具有相同的长度，否则这绝对不起作用。 例如给定一个长度为两条边的最短path，并且在给每条边添加绝对值之后，总path成本增加2 * | max negative weight |。 另一方面，另一条长度为三条边的path，所以path成本增加3 * |最大负重|。 因此，所有不同的path增加了不同的数量。
