使用Dijkstra算法的负权重

Question

我试图理解为什么Dijkstra的算法不能在负权重下工作。阅读有关最短路径的示例，我试图找出以下情况：    2A-------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是贪婪的方法，因此一旦将此顶点标记为已访问顶点，即使以后有另一条花费较少的路径到达该顶点，也永远不会重新评估它。而且，只有当图形中存在负边缘时，才会发生这种问题。

---

一个贪心算法，顾名思义，总是让这似乎是在那一刻的最佳选择。假设您有一个目标函数，需要在给定点进行优化（最大化或最小化）。贪婪算法会在每个步骤中做出贪婪的选择，以确保优化目标函数。贪婪算法只计算一次最优解，因此它永远不会退缩并扭转决策。