使用Dijkstra算法的负权重

Question

我试图理解为什么Dijkstra的算法不能在负权重下工作。阅读有关最短路径的示例，我试图找出以下情况：

    2

A-------B

 \     /

3 \   / -2

   \ /

    C

从网站：

假设所有边都是从左到右定向的，如果我们从A开始，Dijkstra的算法将选择使d（A，A）+ length（edge）最小的边（A，x），即（A，B）。然后设置d（A，B）= 2并选择另一个使d（A，y）+ d（y，C）最小的边（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] ← NIL

   d[s] ← 0

}

Relax(u, v) {

   //update only if we found a strictly shortest path

   if d[v] > d[u] + w(u,v) 

      d[v] ← d[u] + w(u,v)

      π[v] ← u

      Update(Q, v)

}

谢谢，

梅尔

Answer 1

由于Dijkstra是贪婪的方法，因此一旦将此顶点标记为已访问顶点，即使以后有另一条花费较少的路径到达该顶点，也永远不会重新评估它。而且，只有当图形中存在负边缘时，才会发生这种问题。一个贪心算法，顾名思义，总是让这似乎是在那一刻的最佳选择。假设您有一个目标函数，需要在给定点进行优化（最大化或最小化）。贪婪算法会在每个步骤中做出贪婪的选择，以确保优化目标函数。贪婪算法只计算一次最优解，因此它永远不会退缩并扭转决策。