graph-theory - 操纵负加权有向图的边成本以允许使用 Dijkstra 算法

Question

假设我们有一个包含正加权边和负加权边的有向图。

我知道最短路径解决方案是 Bellman-Ford 算法。

我的问题是：为什么我们不能只在所有边成本上添加一些较大的值 N 以便不再有负边，然后使用效率更高的 Dijkstra 算法？

标签： graph-theorydijkstrabellman-forddigraphs

Answer 1

为每个边长添加一个常数对于路径长度来说并不是单调的，即使对于相同的两个节点之间的路径也是如此（因为路径的边数可能不同）。考虑具有边ab、bc和ac权重的图-1。添加N=2切换最短路径从a到c从ab,bc到ac。