具有负权重的 Dijkstra 算法

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

STOP!在你认为“哈哈，你可以在两点之间无休止地跳跃并获得一条无限便宜的路径”之前，我更倾向于考虑单向路径。

其应用是具有点的山区地形。显然，从高到低并不需要能量，事实上，它会产生能量（因此是负路径权重）！但再回去就不行了，除非你是查克·诺里斯。

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

只要图不包含负环（边权重和为负的有向环），任意两点之间就会有一条最短路径，但 Dijkstra 算法并不是为了找到它们而设计的。在具有负边权重的有向图中查找单源最短路径的最著名算法是贝尔曼-福特算法 http://en.wikipedia.org/wiki/Bellman-Ford_algorithm。然而，这是有代价的：贝尔曼-福特需要 O(|V|·|E|) 时间，而迪克斯特拉氏 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm需要 O(|E| + |V|log|V|) 时间，对于稀疏图（其中 E 为 O(|V|)）和稠密图（其中 E 为 O(|V|^2 ））。

在您的山区地形示例中（必然是有向图 http://en.wikipedia.org/wiki/Directed_graph，因为上下斜坡有不同的权重）不存在负循环的可能性，因为这意味着离开一个点，然后以净能量增益返回到该点 - 这可以用来创建一个永动机 http://en.wikipedia.org/wiki/Perpetual_motion.

将所有权重增加一个常数值以使它们成为非负值是行不通的。要了解这一点，请考虑以下图形，其中从 A 到 B 有两条路径，一条路径穿过长度为 2 的单条边，一条穿过长度为 1、1 和 -2 的边。第二条路径较短，但如果将所有边权重增加 2，则第一条路径现在的长度为 4，第二条路径的长度为 6，从而反转最短路径。仅当两点之间的所有可能路径都使用相同数量的边时，此策略才有效。