algorithm - 最短路径距离 -> 如何处理负权重？

Question

我有顶点 V={s,u,v,x} 以及边 E={(s,u),(s,x),(s,v),(u,v),(v ,x),(x,u)) 以及以下权重:

W(s, u) = 1
W(v, x) = W(x, u) = W(s, v)=2
W(u, v) = -3
W(s, x) = -1 

现在我正在执行 Initialize(G,w,s) 以 s 为起点并初始化 s.d = 0。我需要 u、v、x 的最短路径距离。由于它们都连接到 s，我可以只使用 W(s, u)、W(s, v)、W(s, x) 的权重。但是 x.d 将是 -1。那甚至适用吗？我现在可以使用这个距离来正确执行 Relax(s,x,w) 并获得正确的输出吗？

提前致谢

Answer 1

作为Dijkstra's algorithm with negative weights说，只要没有负循环，Bellman-Ford会收敛。如果存在负循环，它将检测到该事实。

如果存在负循环，则没有解决方案，只能将从 A 到 B 的成本与沿途访问的负边集配对，以便您可以追踪它们而不是再次访问它们.这在理论上是正确的，但在内存和运行时间上都很昂贵。