Dijkstra algorithm

presentation on Dijkstra algorithm for shortest path calculation.

1. Dijkstra's Algorithm
We consider a weighted connected simple graphGwith verticesa=v0; v1; : : : ; vn=zand
weightsw(vi; vj)>0 wherew(vi; vj) =1iffvi; vjgis not an edge. Dijkstra's algorithm nds
the cost of the \cheapest" path between verticesaandz.
procedureDijkstra(G: weighted connected simple graph, with all weights positive)
fori= 1ton
L(vi) :=1
L(a) := 0
S:=;
whilez62S
begin
u:= a vertex not inSwithL(u) minimal
S:=S[ fug
forall verticesv62S
ifL(u) +w(u; v)< L(v)thenL(v) :=L(u) +w(u; v)
end
return(L(z))
Example:Use Dijkstra's algorithm to nd the cost of the cheapest path betweenaandzin
the following weighted graph. Describe at each iteration the functionLand setS.
r.
....................................................................................................................................................................................................
r
.
....................................................................................................................................................................................................
r. ............................................................................................................................................................................................................................................................r
. ............................................................................................................................................................................................................................................................r.
....................................................................................................................................................................................................
r
.
.....................................................................................................................................................................................................
........................................................................................................................................................................
.
...................................................................................................................................................................................................................................................................................................................
.
........................................................................................................................................................................
a z
c e
b d
3 4
3
1
2 2
5
16
Solution:The iterations of Dijkstra's algorithm are described in the following table.
SL(a)L(b)L(c)L(d)L(e)L(z);011111fag23111fa; bg3751fa; b; cg741fa; b; c; eg58fa; b; c; e; dg7fa; b; c; e; d; zg
At the last iteration,z2SandL(z) = 7. We conclude that the cheapest path fromatozhas
a cost of 7.
Gilles Cazelais. Typeset with LAT EX on December 2, 2006.