Dÿkstra

For the following graph:

• Fill in the weight matrix, w

  w	s	x	y	z
  s
  x
  y
  z

• Run Dykstra's Algorithm with s as the source. Visit vertices at Line 7 in alphabetical order.

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 ∞ ∞ ∞