Dijkstra's algorithm: Difference between revisions

Revision as of 21:37, 12 May 2004

Revision as of 23:40, 30 May 2004

Line 23:

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

The algorithmbasic also maintains two setsoperation of vertices ''S'Dijkstra's andalgorithm is ''Q''. Setedge relaxation''S'': containsif allthere verticesis foran whichedge we know that the valuefrom ''du''[ to ''v''], is alreadythen the costshortest of the shortestknown path and setfrom ''Qs'' containsto all''u'' othercan vertices.be extended

to a path from ''s'' to ''v'' by adding edge (''u'',''v'') at the end. This path will have length ''d''[''u'']+''w''(''u'',''v''). If this is less than

''d''[''v''], we can replace current value of ''d''[''v''] with the new value.

Edge relaxation is applied until all values ''d''[''v''] represent the cost of the shortest path from ''s'' to ''v''. The algorithm is organized so that each edge (''u'',''v'') is relaxed only once, when ''d''[''u''] has reached its final value.

The algorithm 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 forrelaxes 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==