的例子，Dijkstra算法将正常工作

-3

这不是问题的另一个副本，试图理解，为什么Dijkstra算法不能负权重的工作。我知道为什么，但在某些特殊情况下，它会使用负面权重，我试图找到它们。的例子，Dijkstra算法将正常工作

因此，在某些情况下，Dijkstra算法可以正确地与负权图的工作，但我无法找到例子。有谁知道图表，这将工作？

2016-01-29 TheColloto

那么Dijkstra算法，如果以简单的方式实现的（每次一个节点是放松的，它被添加到PQ）总能工作，除非有一个负循环从源头到达。但是对于非负面情况的运行时间保证不成立，因为一个节点可以被处理多次，算法本质上变成了节点 –

@NiklasB。使用Dijkstra每个节点只处理一次。即使在没有负循环的情况下，负加权边缘也可能导致计算失败。这就是为什么一般来说负面权重不起作用的原因。也许你在想约翰逊的算法？ https://en.wikipedia.org/wiki/Johnson%27s_algorithm –

@ ErickG.Hagstrom算法有不同的表达式。在实践中，如果使用优先级队列，那么不明确地跟踪已经完成的节点是有意义的，因此您可以在理论上*再次放松已定义的节点，但这绝不会发生在非负向图上。它可以发生在负权重上，但不会损害正确性（如果没有负循环）。也许我在这里稍微扩展了“Dijkstra算法”的概念 –

一个简单的例子，使得Dijkstra算法正常工作与负重量，简直是：

s -(-1)-> t

如果运行Dijkstra的从源s这个图形算法，它会发现t为最近的邻居，并选择一个，然后我们构建了正确的最短路径树。

来源

2016-01-29 20:47:08

事实上它只有在对原产start将工作边负权重的任何图形。负权重的问题在于它们可能导致算法“错过”最低权重顶点，因为它在“稍后”得到较低的权重。所以

| begin | end | weight | 
| s | 1 | -1 | 
| s | 2 | -2 | 
| 1 | 3 | 1 | 
| 2 | 3 | 1 | 
| 3 | t | 1 |

应该没有实际的麻烦给迪克斯特拉。

我们可以将其推广到一个更强有力的陈述：在Dijkstra评估之前正确计算顶点权重的任何图都将由Dijkstra正确处理，保留Dijkstra的时间表现。

来源

2016-01-29 21:26:42

的例子，Dijkstra算法将正常工作

回答

相关问题