The shortest path algorithm is given a weighted graph or digraph G = (V,E,W) and two specified vertices v and w; the algorithm finds a shortest path from v to w. The distance from a vertex v to a vertex w (denoted d(v,w)) is the weight of a shortest path from v to w. Dijkstra's shortest path algorithm will find shortest paths from v to the other vertices in order of increasing distance from v. The algorithm stops when it reaches w.

The algorithm starts a one vertex (v) and "branches out" by selecting certain edges that lead to new vertices. It is also an example of a "greedy" algorithm -- it always chooses an edge to a vertex that appears to be closest.

Check other topics for the shortest path algorithm. They are all important.

Back to AlgoNet Home