Content deleted Content added
mNo edit summary |
m disambig link, doesn't link properly |
||
Line 7:
The cost of a path between two vertices is the sum of costs of the edges in that path. The cost of an edge can be thought of as (a generalisation of) the distance between those two vertices. For a given pair of vertices s,t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path).
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<sub>i</sub> = (v<sub>i1</sub>,v<sub>i2</sub>) in G-S such that v<sub>i1</sub> is in S and v<sub>i2</sub> is in G, and then (b) choosing the edge e<sub>j</sub> = (v<sub>j1</sub>,v<sub>j2</sub>) in G-S which gives the minimum distance of its vertex v<sub>j2</sub> (in G) from s from all edges e<sub>i</sub>. 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 procedure for adding an edge e<sub>j</sub> to S maintains the property that the distances of all the vertices within S from s are '''known''' to be minimum.
| |||