Dijkstra's Shortest Path Algorithm
One algorithm for finding the shortest path from a starting node to a target node in a weighted graph is Dijkstra’s algorithm. The algorithm creates a tree of shortest paths from the starting vertex, the source, to all other points in the graph.
Dijkstra’s algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected. One stipulation to using the algorithm is that the graph needs to have a nonnegative weight on every edge.
Suppose a student wants to go from home to school in the shortest possible way. She knows some roads are heavily congested and difficult to use. In Dijkstra's algorithm, this means the edge has a large weightthe shortest path tree found by the algorithm will try to avoid edges with larger weights. If the student looks up directions using a map service, it is likely they may use Dijkstra's algorithm, as well as others.
Find the shortest path from home to school in the following graph:
The shortest path, which could be found using Dijkstra's algorithm, is
\[\text{Home} \rightarrow B \rightarrow D \rightarrow F \rightarrow \text{School}.\ _\square\]
Dijkstra's Algorithm
Dijkstra’s algorithm finds a shortest path tree from a single source node, by building a set of nodes that have minimum distance from the source.
The graph has the following:
 vertices, or nodes, denoted in the algorithm by \(v\) or \(u\);
 weighted edges that connect two nodes: (\(u,v\)) denotes an edge, and \(w(u,v)\) denotes its weight. In the diagram on the right, the weight for each edge is written in gray.
This is done by initializing three values:
 \(dist\), an array of distances from the source node \(s\) to each node in the graph, initialized the following way: \(dist\)(\(s\)) = 0; and for all other nodes \(v\), \(dist\)(\(v\)) = \(\infty\). This is done at the beginning because as the algorithm proceeds, the \(dist\) from the source to each node \(v\) in the graph will be recalculated and finalized when the shortest distance to \(v\) is found
 \(Q\), a queue of all nodes in the graph. At the end of the algorithm's progress, \(Q\) will be empty.
 \(S\), an empty set, to indicate which nodes the algorithm has visited. At the end of the algorithm's run, \(S\) will contain all the nodes of the graph.
The algorithm proceeds as follows:
 While \(Q\) is not empty, pop the node \(v\), that is not already in \(S\), from \(Q\) with the smallest \(dist\) (\(v\)). In the first run, source node \(s\) will be chosen because \(dist\)(\(s\)) was initialized to 0. In the next run, the next node with the smallest \(dist\) value is chosen.
 Add node \(v\) to \(S\), to indicate that \(v\) has been visited
 Update \(dist\) values of adjacent nodes of the current node \(v\) as follows: for each new adjacent node \(u\),
 if \(dist\) (\(v\)) + \(weight(u,v)\) < \(dist\) (\(u\)), there is a new minimal distance found for \(u\), so update \(dist\) (\(u\)) to the new minimal distance value;
 otherwise, no updates are made to \(dist\) (\(u\)).
The algorithm has visited all nodes in the graph and found the smallest distance to each node. \(dist\) now contains the shortest path tree from source \(s\).
Note: The weight of an edge (\(u,v\)) is taken from the value associated with (\(u,v\)) on the graph.
Implementation
This is pseudocode for Dijkstra's algorithm, mirroring Python syntax. It can be used in order to implement the algorithm in any language.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

Examples
We step through Dijkstra's algorithm on the graph used in the algorithm above:
Initialize distances according to the algorithm.
Pick first node and calculate distances to adjacent nodes.
Pick next node with minimal distance; repeat adjacent node distance calculations.
Final result of shortestpath tree
Run Dijkstra's on the following graph and determine the resulting shortest path tree.
Dijkstra will visit the vertices in the following order: \(S,C,A,D,F,E,B\). The closer edges will be relaxed first. As a result, the parent of each node is as follows:
We describe the ice rink using the following notation:
(#)  Wall
(.)  Free space
(S)  Sally's starting position
(D)  Dad's position.
For example, in the following ice rink, the shortest path is 18 steps.
Here is a text file of 5 ice rinks of size \( 20 \times 20 \). The rinks are separated by hyphens.
Find the sum of the shortest paths of these five \( 20 \times 20 \) ice rinks.
Note: Sally has to stop at her father's position. She will slide past him if there are no walls.
Image credit: Flickr Saad Akhtar
References
 Skiena, S. Dijkstra's Algorithm Animation. Retrieved April 22, 2016, from http://www3.cs.stonybrook.edu/~skiena/combinatorica/animations/anim/dijkstra.gif
 Hall, A. How to use Dijkstra's algorithm. Retrieved April 27, 2016, from https://www.youtube.com/watch?v=Cjzzx3MvOcU
 Hazzard, E. Tutorial. Retrieved April 24, 2016, from http://vasir.net/static/tutorials/shortest\<em>path/shortest\</em>path2\<em>1\</em>a\_selected.png
 Hazzard, E. Tutorial. Retrieved April 24, 2016, from http://vasir.net/static/tutorials/shortest\<em>path/shortest\</em>path2\<em>1\</em>a\<em>selected\</em>3.png
 Hazzard, E. Tutorial. Retrieved April 24, 2016, from http://vasir.net/static/tutorials/shortest\<em>path/shortest\</em>path3\_2.png
 Hazzard, E. Tutorial. Retrieved April 24, 2016, from http://vasir.net/static/tutorials/shortest\<em>path/shortest\</em>path\_final.png