Dijkstra's algorithm

From Mathematics

Dijkstra's algorithm is one of the most widely used methods for finding single-source shortest paths in a simple digraph. In other words, Dijkstra's algorithm determines the shortest paths from a common vertex to all other vertices in a digraph, if they exist.

Contents 1 Algorithm 1.1 Initial Stage 1.2 Iterative Stage 2 Additional Details 2.1 Interpretation of Results 2.2 Non-negativity Constraint 2.3 Dynamic Programming 3 Notes

[edit] Algorithm

Let be a simple digraph with a function which assigns a weight, a non-negative real number, to each arc in . Fix a source vertex in , from which shortest paths will be found.

Additionally, for the purposes of the search itself, let denote the length of the shortest path from to . Let denote the set of visited vertices, i.e., those vertices that have already been examined by the algorithm. Given a path in determined by the algorithm, let denote the predecessor of for any in such that . The meanings of these additions will become clear in the description of the algorithm. The execution proceeds as follows.

[edit] Initial Stage

1. Let . ^[1]
2. For each vertex adjacent from , let be , and let .
3. For each vertex such that and is not adjacent from , let . ^[2]
4. Let . ^[3]

[edit] Iterative Stage

1. Determine the vertex that minimizes in , i.e., an unvisited vertex.
2. For each vertex adjacent from , compare the current value and . If is the least of the two, let , and let .
3. Mark as visited. That is, let .
4. If , all vertices have been visited; halt. Otherwise, return to the first step.

[edit] Additional Details

[edit] Interpretation of Results

When the execution terminates, every vertex for which has a shortest path. This shortest path is determined by repeated application of to . For instance, a shortest path from to , four vertices long, would be described . For any vertex where , there is, of course, no shortest path from to .

[edit] Non-negativity Constraint

Because Dijkstra's algorithm is a special case of uniform cost search, where there is no particular goal state, it is essential that for all arcs in .

[edit] Dynamic Programming

Dijkstra's algorithm is also an instance of dynamic programming.^[4] Let equal the value of in the th iteration of the algorithm, where initially and . Let denote the weight of the shortest path from to , given the knowledge of . Then

Therefore, the purpose of Dijkstra's algorithm is to determine the best policy for transforming the state of the problem (i.e., which vertex to move to next). It does so by refining an approximation of the best shortest-path policy for all vertices with each iteration, until the full solution is realized. The algorithm is efficient in practice because each iteration relies on previously determined information.

[edit] Notes

1. ↑ ...since there is no effort in staying in place.
2. ↑ That is, the distance is unknown and is assumed to be unreachable until it is proven otherwise.
3. ↑ ...since no paths from to itself need to be considered.
4. ↑ To preempt any accusations of plagiarism, the description that follows was cribbed by the author from an article he himself wrote on PlanetMath.