Dijkstra's Algorithm
dijkstra.cpp

Dijkstra's Algorithm is used in many contexts. The classic way of explaining it is that it is probably used, in some form, in all GPS-type navigation devices.

Mathematically, the basic construct of the algorithm is to consider a graph, a set of points with edges connecting some or all of the points. An edge connects only its endpoints; a path is made up by a series of edges where the ending point of one edge is the starting point of another. For example, a path might be from New York City to Washington DC to Atlanta to Tallahassee. This path has three edges.

What makes the algorithm interesting is that each path has a cost. The cost is arbitrary; it is only important that any two costs can be compared.

For instance, the cost could be distance. In this case the cost from New York to Philadelphia would be less than the cost from Philadelphia to Atlanta. Clever routing algorithms would merge other factors into this cost, such as traffic, weather, road conditions, etc. For the algorithm it is only important that a measurable cost exists.

So what is the algorithm anyway.

Like all algorithms, Dijkstra's is a recipe. His recipe provably guarantees to calculate the shortest (in terms of cost) path from a known starting point to any other point.

The algorithm works by maintaining two sets: a set of known shortest paths and a set of candidates for that list. The elements of each set are a node (point) name and the cost of the path to reach that node. Optionally information can be kept that enables the path to be reconstructed. Storing the name of the
preceding node on the path suffices for this.

1. Initialize the candidate set with (N0, 0) where N0 is the starting node and 0 is the cost to reach that node.
2. Remove the lowest cost (node, cost) pair from the candidate set.
3. If that node is in the shortest-path set, then a shortest path has already been found so discard it and go back to step 2.
4. If this node is not in the shortest-path set, a shortest path to this node has been found, so add the pair (node, cost) to the shortest-path set.
5. Find all the edges from this node to neighbor nodes that have not already been found. For each edge add the pair (end-node, new-cost) to the candidate set, where end-node is the node where the new edge ends and new-cost is the sum  of the cost to the edge starting node (i.e. the last-found shortest path cost) plus the cost of the new edge.
6. Go back to step 2.

Notes:
• There may be two or more paths with the same shortest value. The algorithm does not determine which one is found, only that one of them will be.
• (node, cost) pairs will be added to the shortest-path set in order of increasing-or-equal cost
• The node last added to the shortest-path set is always used to generate new candidate pairs.
• The next qualifying candidate may not be one of the just-generated ones, but may have been one generated earlier which has now 'bubbled to the top' of the candiate list.
• All nodes may not be reachable from the starting node.
• The wikipedia article on Dijkstra's algorithm can be found here.
 [ Previous  |  Next ]     [ Up  |  First  |  Last ]     (Article 9 of 485)