负权重的 Dijkstra 算法

Question

我们可以使用负权重的 Dijkstra 算法吗？

停止! 在您认为“大声笑，您可以在两点之间无休止地跳跃并获得无限便宜的路径”之前，我更多地考虑的是单向路径。

对此的应用程序将是一个带有点的山地地形。显然从高到低不需要能量，事实上，它会产生能量(因此路径权重为负)!但是再次回去是行不通的，除非你是查克诺里斯。

我正在考虑增加所有点的权重，直到它们为非负值，但我不确定这是否有效。

Answer 1

只要图不包含负环(边权重为负的有向环)，它就会有任意两点之间的最短路径，但 Dijkstra 算法并不是为了找到它们。在具有负边权重的有向图中寻找单源最短路径的最著名算法是 Bellman-Ford algorithm .然而，这是有代价的:Bellman-Ford 需要 O(|V|·|E|) 时间，而 Dijkstra's需要 O(|E| + |V|log|V|) 时间，对于稀疏图(其中 E 是 O(|V|))和密集图(其中 E 是 O(|V|^2 ))。

在您的山地地形示例中(必须是 directed graph ，因为上下斜坡具有不同的权重)不可能出现负循环，因为这意味着离开一个点然后以净能量返回该点增益 - 可用于创建 perpetual motion machine .

将所有权重增加一个恒定值，使其为非负值是行不通的。要看到这一点，请考虑从 A 到 B 有两条路径的图，一条穿过长度为 2 的单边，另一条穿过长度为 1、1 和 -2 的边。第二条路径较短，但如果将所有边的权重增加 2，则第一条路径的长度现在为 4，第二条路径的长度为 6，将最短路径颠倒过来。只有当两点之间所有可能的路径都使用相同数量的边时，这种策略才有效。