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.

Dijkstra's algorithm in action on a non-directed graph ^[1]

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:

A weighted graph representing roads from home to school ^[2]

---

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 finds a shortest path tree from a single source node, by building a set of nodes that have minimum distance from the source.

Graph ^[3]

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:

1. 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.
2. Add node \(v\) to \(S\), to indicate that \(v\) has been visited
3. 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.

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

function Dijkstra(Graph, source):
       dist[source]  := 0                     // Distance from source to source is set to 0
       for each vertex v in Graph:            // Initializations
           if v ≠ source
               dist[v]  := infinity           // Unknown distance function from source to each node set to infinity
           add v to Q                         // All nodes initially in Q

      while Q is not empty:                  // The main loop
          v := vertex in Q with min dist[v]  // In the first run-through, this vertex is the source node
          remove v from Q 

          for each neighbor u of v:           // where neighbor u has not yet been removed from Q.
              alt := dist[v] + length(v, u)
              if alt < dist[u]:               // A shorter path to u has been found
                  dist[u]  := alt            // Update distance of u 

      return dist[]
  end function

We step through Dijkstra's algorithm on the graph used in the algorithm above:

1. Initialize distances according to the algorithm. ^[3]

2. Pick first node and calculate distances to adjacent nodes. ^[4]

3. Pick next node with minimal distance; repeat adjacent node distance calculations. ^[5]

4. Final result of shortest-path tree ^[6]

Question

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: Solution

1. Skiena, S. Dijkstra's Algorithm Animation. Retrieved April 22, 2016, from http://www3.cs.stonybrook.edu/~skiena/combinatorica/animations/anim/dijkstra.gif
2. Hall, A. How to use Dijkstra's algorithm. Retrieved April 27, 2016, from https://www.youtube.com/watch?v=Cjzzx3MvOcU
3. 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
4. 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
5. Hazzard, E. Tutorial. Retrieved April 24, 2016, from http://vasir.net/static/tutorials/shortest\<em>path/shortest\</em>path3\_2.png
6. Hazzard, E. Tutorial. Retrieved April 24, 2016, from http://vasir.net/static/tutorials/shortest\<em>path/shortest\</em>path\_final.png