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 weight--the 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
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 or ;
- weighted edges that connect two nodes: () denotes an edge, and 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:
- , an array of distances from the source node to each node in the graph, initialized the following way: () = 0; and for all other nodes , () = . This is done at the beginning because as the algorithm proceeds, the from the source to each node in the graph will be recalculated and finalized when the shortest distance to is found
- , a queue of all nodes in the graph. At the end of the algorithm's progress, will be empty.
- , an empty set, to indicate which nodes the algorithm has visited. At the end of the algorithm's run, will contain all the nodes of the graph.
The algorithm proceeds as follows:
- While is not empty, pop the node , that is not already in , from with the smallest (). In the first run, source node will be chosen because () was initialized to 0. In the next run, the next node with the smallest value is chosen.
- Add node to , to indicate that has been visited
- Update values of adjacent nodes of the current node as follows: for each new adjacent node ,
- if () + < (), there is a new minimal distance found for , so update () to the new minimal distance value;
- otherwise, no updates are made to ().
The algorithm has visited all nodes in the graph and found the smallest distance to each node. now contains the shortest path tree from source .
Note: The weight of an edge () is taken from the value associated with () on the graph.
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
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 shortest-path tree
Run Dijkstra's on the following graph and determine the resulting shortest path tree.
Dijkstra will visit the vertices in the following order: . The closer edges will be relaxed first. As a result, the parent of each node is as follows:
Sally is a very bad skater, so she can only skate in one direction! But Sally still wants to find her dad in the least amount of moves possible so that she can get off the ice. Sally's only way of stopping is (crashing into) walls or the edge of the ice rink.
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 ice rink at right, the shortest path is 18 steps.
Here is a text file of 5 ice rinks of size . The rinks are separated by hyphens.
Find the sum of the shortest paths of these five 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
- 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