Dijkstra's algorithm: Difference between revisions

Revision as of 02:06, 30 April 2004

Revision as of 02:30, 30 April 2004

Line 29:

==Pseudocode==

A few subroutines for use with Dijkstra's algorithm:

In the following algorithm,

Initialize-Single-Source(G,s)

vu := Extract-Min(Q) searches for the vertex v''u'' in the vertex set ''Q'' that has the least ''d''[v''u''] value. That vertex is removed from the set ''Q'' and then returned.

1 '''for''' each vertex v in V[G]

2 '''do''' d[v] := infinite

3 previous[v] := 0

4 d[s] := 0

Dijkstra(''G'',''w'',''s'')

Relax(u,v,w)

1 '''iffor''' d[each vertex v] >in dV[uG] + w(u,v)

2 '''thendo''' d[v] := d[u] + w(u,v)infinity

3 previous[v] := uundefined

4 d[s] := 0

25 S := empty set

36 Q := set of all vertices

7 '''while''' Q is not an empty set

28 '''do''' d[v]u := infiniteExtract-Min(Q)

69 S := S union {u}

110 '''for''' each vertex v inwhich is a neighbour of V[G]u

811 '''do''' Relax'''if''' d[v] > d[u] + w(u,v,w)

12 '''then''' d[v] = d[u] + w(u,v)

313 previous[v] := 0u

If we are only interested in a shortest path between vertexesvertices ''s'' and ''t'', we can terminate the search at line 58 if ''u'' == ''t''.

v = Extract-Min(Q) searches for the vertex v in the vertex set Q that has the least d[v] value. That vertex is removed from the set Q and then returned.

Now we can read the shortest path from ''s'' to ''t'' by iteration:

The algorithm:

1 ''S'' = empty sequence

Dijkstra(G,w,s)

2 u := t

1 Initialize-Single-Source(G,s)

3 S = u + S /* insert ''u'' to the beginning of ''S */''

2 S := empty set

4 '''if''' ''u'' == ''s''

3 Q := set of all vertices

45 '''whileend''' Q is not an empty set

6 ''u'' = previous[''u'']

5 '''do''' u := Extract-Min(Q)

6 S := S union {u}

7 '''for''' each vertex v which is a neighbour of u

8 '''do''' Relax(u,v,w)

If we are only interested in a shortest path between vertexes s and t, we can terminate the search at line 5 if u == t.

Now we can read the shortest path from s to t by iteration:

1 S = empty sequence

2 u := t

3 S = u + S /* insert u to the beginning of S */

4 '''if''' u == s

5 end

6 u = previous[u]

7 goto 3

Now sequence ''S'' has the shortest path from ''s'' to ''t''.

== Running time==