Content deleted Content added
m +seealso |
hint at proof ... |
||
Line 3:
Assume that the function w: V x V -> [0, ∞] describes the cost w(x,y) of moving from vertex x to [[vertex]] y (non-negative cost). (We can define the cost to be infinite for pairs of vertices that are not connected by an edge.) For a given vertex s in V, the algorithm computes the shortest path (lowest total value of w) from s to any other vertex t.
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 ei = (vi1,vi2) in G-S such that vi1 is in S and vi2 is in G, and then (b) choosing the edge ej = (vj1,vj2) in G-S which gives the minimum distance of its vertex vj2 (in G) from s from all edges ei. The algorithm terminates either when S becomes a spanning tree of G, or when all the vertices of interest are within S.
The procedure for adding an edge ej to S maintains the property that the distances of all the vertices within S from s are '''known''' to be minimum.
A few subroutines for use with Dijkstra's algorithm:
| |||