Catalogue of Artificial Intelligence Techniques
Keywords: dijkstra; shortest path;
Author(s): Chris Conway
Used on a directed or undirected graph to find the shortest path from one vertex to another, where each edge has a weighting which is non-negative. It stores a sum of the minimum cost edges.
It is often used in the context where each vertex is a city and the edges represent the roads between the cities, with weightings representing the distance or cost of traveling on these roads. The algorithm is applied to find the shortest or most inexpensive route from a city A to a city B.
The algorithm maintains two sets of vertices - one whose shortest-path weights have been calculated (set S - initially empty) and one who's are still to be determined (set Q - initially containing all the vertices in the graph). At each step, a vertex from Q is chosen to be moved to S if it is the vertex with the lowest cost from the start vertex - when this vertex is moved, the algorithm begins working out the shortest path from the moved vertex to the final vertex. The final weighting is calculated by the summation of all the vertices in set S.
Real world implementations are used on the internet to route traffic based on the open shortest path first protocol.
- Cormen et. al., Introduction to Algorithms, MIT Press and McGraw Hill, 2001.