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             p[v] ¬ u   s x y z p NIL NIL NIL NIL d 0 ¥ ¥ ¥

Solution

s x y z p NIL NIL NIL NIL d 0 ¥ ¥ ¥ Q = V = sxyz   S = Æ	1)   s x y z p NIL s NIL s d 0 3 ¥ 8 u=s   Q=xzy     S = { s }
2)   s x y z p NIL s x x d 0 3 5 7 u=x      Q=yz      S = { s, x }	3)   s x y z p NIL s x y d 0 3 5 6 u=y      Q=z    S = { s, x, y }
4)   s x y z p NIL s x y d 0 3 5 6 u=z     Q=Æ        S = { s, x, y, z }