我试图理解为什么 Dijkstra 的算法不适用于负权重。阅读有关Shortest Paths的示例,我试图找出以下情况:
2
A-------B
\ /
3 \ / -2
\ /
C
从网站:
假设边都是从左到右的,如果我们从 A 开始,Dijkstra 的算法会选择边 (A,x) 最小化 d(A,A)+length(edge),即 (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] ← 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)
}
谢谢,
梅尔