Dijkstra's algorithm: Difference between revisions

Revision as of 01:15, 30 April 2004

Revision as of 01:35, 30 April 2004

Line 17:

==Description of the algorithm==

The algorithm works by constructing a subgraph S of such that the distance of any vertex v' (in S) from s is '''known''' to be a minimum within G. Initially S is simply the single vertex s, and the distance of s from itself is known to be zero. Edges are added to S at each stage by (a) identifying all the edges e_i = (v_i1,v_i2) in G-S such that v_i1 is in S and v_i2 is in G, and then (b) choosing the edge e_j = (v_j1,v_j2) in G-S which gives the minimum distance of its vertex v_j2 (in G) from s from all edges e_i. The algorithm terminates either when S becomes a [[spanning tree (mathematics)|spanning tree]] of G, or when all the vertices of interest are within S.

The algorithm works by keeping for each vertex ''v'' the cost ''d''[''v''] of the shortest path found so far. Initially, this value is 0 for the source vertex ''s''

The procedure for adding an edge e_j to S maintains the property that the distances of all the vertices within S from s are '''known''' to be minimum.

and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices. When the algorithm finishes, ''d''[''v''] will be

the cost of the shortest path from ''s'' to ''v'' or infinity, if no such path exists.

The algorithm also maintains two sets of vertices ''S'' and ''Q''. Set ''S'' contains all vertices for which we know that the value ''d''[''v''] is already the cost of the shortest path and set ''Q'' contains all other vertices.

Set ''S'' starts empty, and in each step one vertex is moved from ''Q'' to ''S''. This vertex chosen as the vertex with lowest value of ''d''[''u''].

When a vertex ''u'' is moved to ''S'', the algorithm checks for every

outgoing edge (''u'',''v''), whether it cannot be used to create a path

with lower cost than the cost currently stored in ''d''[''v''].

==Pseudocode==