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

提前致谢

Answer 1

正如带负权重的 Dijkstra 算法所说，只要没有负环，Bellman-Ford就会收敛。如果存在负循环，它将检测到该事实。

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