Diikstra's algorithm d]∈-0 for each y∈-{s} do dvI S< Q← Q is a priority queue maintaining V-S while≠⑧ do← EXTRACT-MIN(Q S←SU{ for each y∈Ao/ do if dv> du+w(u, v) relaxation then dlv]<d[u]+w(u, v) step Implicit dECrEase-Key c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17. 8© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.8 Dijkstra’s algorithm d[s] ← 0 for each v ∈ V – {s} do d[v] ← ∞ S ← ∅ Q ← V ⊳ Q is a priority queue maintaining V – S while Q ≠ ∅ do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) relaxation step Implicit DECREASE-KEY