在这种情况下，目标是找到一条总权重最小的路径。共有5个部分，每个部分具有不同的节点。节点仅连接到相邻节中的节点，并且路径必须仅由每个节中的单个节点组成。
例如，让：
- 第1节有节点[1，2，3]
- 第2节具有节点[4，5]
- 第3节具有节点[6]
- 第4节具有节点[7，8，9，10，11]
- 第5节具有节点[12，13，14]
通过区段的有效路径是[1，4，6，7，12]以及[1，5，6，11，14]等。
所有节点都具有负权重，但负循环是不可能的(由于每节一个节点的策略(。因此，向每个节点添加常量的过程是否解决了负权重的问题？如果它能解决这个问题，有没有文件显示这一点？我知道还有其他算法可以解决负权重，但我对Dijkstra的算法很感兴趣。谢谢
不，您不能这样做。让我们看看反例。假设我们有一个具有A、B、C节点和egdes:的图
A - B -2 (negative)
A - C 6
B - C 7
我们正在寻找从CCD_ 4到CCD_ 5的最短路径。在原始图中，我们有
A - B - C => -2 + 7 = 5 (the shortest path, 5 < 6)
A - C => 6
最佳选择为A - B - C。现在，让我们通过添加2来消除负边。我们现在有
A - B 0
A - C 8
B - C 9
A - B - C => 0 + 9 = 9
A - C => 8 (the shortest path, 8 < 9)
请注意，现在最短路径是A - C。唉！在将常数值添加到每条边的同时，我们破坏问题本身；现在我们使用哪种算法已经不重要了。
编辑：所有边(弧以防止负循环(为负的反例：
A -> B -6
B -> C -1
A -> C -5
在添加6之前，我们有
A -> B -> C = -6 - 1 = -7 (the shortest path)
A -> C = -5
添加6后，我们得到
A -> B 0
B -> C 5
A -> C 1
A -> B -> C = 0 + 5 = 5
A -> C = 1 (the shortest path)