Dÿkstra

powered by FreeFind

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