Dÿkstra

For the following graph:

• Fill in the weight matrix, w

  w	s	x	y	z
  s	∞	3	∞	8
  x	∞	∞	2	4
  y	∞	∞	∞	1
  z	1	∞	∞	∞

• Run Dykstra's Algorithm with s as the source.

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 }