D˙kstra

Document last modified: 

For the following graph:

  D˙kstra(V, E, w, s)
1 Init-Single-Source(V, s)
2 S ← ∅
3 Q ← V
4 while Q ≠ |
5    do u ← Extract-Min( Q )
6         S ← S ∪ { u }
7         for each vertex v ∈ Adj[ u ]
8               do Relax(u, v, w)
  RELAX(u, v, w)
1 if d[ v ] > d[ u ] + w(u, v)
2     then d[ v ] d[ u ] + w(u, v)
3             π[v] u
  s x y z
π NIL NIL NIL NIL
d 0

Solution
 
  s x y z
π NIL NIL NIL NIL
d 0

Q = V = sxyz   S = |

1)
  s x y z
π NIL s NIL s
d 0 3 8

u=s   Q=xzy     S = { s }

2)
  s x y z
π NIL s x x
d 0 3 5 7

u=x      Q=yz      S = { s, x }

3)
  s x y z
π NIL s x y
d 0 3 5 6

u=y      Q=z    S = { s, x, y }

4)
  s x y z
π NIL s x y
d 0 3 5 6

u=z     Q=|        S = { s, x, y, z }