相关疑难解决方法(0)

我试图理解为什么Dijkstra的算法不适用于负权重.阅读最短路径上的示例,我试图找出以下场景:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

来自网站:

假设边缘全部从左向右指向,如果我们从A开始,Dijkstra算法将选择最小化d(A,A)+长度(边缘)的边(A,x),即(A,B).然后设置d(A,B)= 2并选择另一个边(y,C),使d(A,y)+ d(y,C)最小化; 唯一的选择是(A,C),它设置d(A,C)= 3.但它从未找到从A到B的最短路径,通过C,总长度为1.

我无法理解为什么使用Dijkstra的以下实现,d [B]将不会更新为1(当算法到达顶点C时,它将在B上运行放松,看到d [B]等于2,因此更新它的价值1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ? Ø
   Q ? V[G]//priority queue by d[v]
   while Q ? Ø do
      u ? Extract-Min(Q)
      S ? S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v ? V(G)
      d[v] ? ?
      ?[v] …

我最近一直在研究全对最短路径算法,例如Floyd-Warshall和Johnson算法,我注意到即使图形包含负权重边(但不是负权重周期),这些算法也会产生正确的解.为了比较,Dijkstra的算法(单源最短路径)不适用于负权重边缘.是什么让所有对最短路径算法与负权重一起工作？

给定一个具有负权重的图表,但我们确定它没有负周期:

为所有权重添加足够大的常量,使它们现在为正,并使用Dijkstra算法找到最小路径.

如果我们没有负循环,上述是否正确？如果我们有负循环,我们就不能使用该算法,因为它需要重新访问标记为已完成的节点Dijkstra.