Dijkstra's algorithm

Primary authors of this description: A.N.Daryin.

1 Properties and structure of the algorithm

1.1 General description of the algorithm

Dijkstra's algorithm was designed for finding the shortest paths between nodes in a graph. For a given weighted digraph with nonnegative weights, the algorithm finds the shortest paths between a singled-out source node and the other nodes of the graph.

Dijkstra's algorithm (using Fibonacci heaps ) is executed in [math]O(m + n \ln n)[/math] time and, asymptotically, is the fastest of the known algorithms for this class of problems.

1.2 Mathematical description of the algorithm

Let [math]G = (V, E)[/math] be a given graph with arc weights [math]f(e)[/math] and the single-out source node [math]u[/math]. Denote by [math]d(v)[/math] the shortest distance between the source [math]u[/math] and the node [math]v[/math].

Suppose that one has already calculated all the distances not exceeding a certain number [math]r[/math], that is, the distances to the nodes in the set [math]V_r = \{ v \in V \mid d(v) \le r \}[/math]. Let

[math] (v, w) \in \arg\min \{ d(v) + f(e) \mid v \in V, e = (v, w) \in E \}. [/math]

Then [math]d(w) = d(v) + f(e)[/math] and [math]v[/math] lies on the shortest path from [math]u[/math] to [math]w[/math].

The values [math]d^+(w) = d(v) + f(e)[/math], where [math]v \in V_r[/math], [math]e = (v, w) \in E[/math], are called expected distances and are upper bounds for the actual distances: [math]d(w) \le d^+(w)[/math].

Dijkstra's algorithm finds at each step the node with the least expected distance, marks this node as a visited one, and updates the expected distances to the ends of all arcs outgoing from this node.

1.3 Computational kernel of the algorithm

The basic computations in the algorithm concern the following operations with priority queues:

• retrieve the minimum element (delete_min);
• decrease the priority of an element (decrease_key).

1.4 Macro structure of the algorithm

Pseudocode of the algorithm:

Input data:
  graph with nodes V and arcs E with weights f(e);
  source node u.
Output data: distances d(v) to each node v ∈ V from the node u.

Q := new priority queue
for each v ∈ V:
    if v = u then d(v) := 0 else d(v) := ∞ 
    Q.insert(v, d(v))

while Q ≠ ∅:
    v := Q.delete_min()
    for each e = (v, w) ∈ E:
        if d(w) > d(v) + f(e):
            d(w) := d(v) + f(e)
            Q.decrease_key(w, d(w))

1.5 Implementation scheme of the serial algorithm

A specific implementation of Dijkstra's algorithm is determined by the choice of an algorithm for priority queues. In the simplest case, it can be an array or a list in which search for the minimum requires the inspection of all nodes. Algorithms that use heaps are more efficient. The variant using Fibonacci heaps has the best known complexity estimate.

It is possible to implement the version in which nodes are added to the queue at the moment of the first visit rather than at the initialization stage.

1.6 Serial complexity of the algorithm

The serial complexity of the algorithm is [math]O(C_1 m + C_2n)[/math], where

• [math]C_1[/math] is the number of operations for decreasing the distance to a node;
• [math]C_2[/math] is the number of operations for calculating minima.

The original Dijkstra's algorithm used lists as an internal data structure. For such lists, [math]C_1 = O(1)[/math], [math]C_2 = O(n)[/math], and the total complexity is [math]O(n^2)[/math].

If Fibonacci heaps are used, then the time for calculating a minimum decreases to [math]C_2 = O(\ln n)[/math] and the total complexity is [math]O(m + n \ln n)[/math], which, asymptotically, is the best known result for this class of problems.

1.7 Information graph

Figure 1 shows the graph of the basic implementation of Dijkstra's algorithm based on lists or arrays.

Figure 1. Information graph of Dijkstra's algorithm. The input and output data are not shown. n=3. Comparison operations, operations for changing node labels, and node labeling operations are indicated in yellow, green, and blue, respectively.

1.8 Parallelization resource of the algorithm

Dijkstra's algorithm admits an efficient parallelization Its average execution time is [math]O(n^{1/3}\ln n)[/math], and the computational complexity is [math]O(n \ln n + m)[/math].

The algorithm of Δ-stepping can be regarded as a parallel version of Dijkstra's algorithm.

1.9 Input and output data of the algorithm

Input data: weighted graph [math](V, E, W)[/math] ([math]n[/math] nodes [math]v_i[/math] and [math]m[/math] arcs [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] with weights [math]f_j[/math]), source node [math]u[/math].

Size of input data: [math]O(m + n)[/math].

Output data (possible variants):

1. for each node [math]v[/math] of the original graph, the last arc [math]e^*_v = (w, v)[/math] lying on the shortest path from [math]u[/math] to [math]v[/math] or the corresponding node [math]w[/math];
2. for each node [math]v[/math] of the original graph, the summarized weight [math]f^*(v)[/math] of the shortest path from [math]u[/math] to [math]v[/math].

Size of output data: [math]O(n)[/math].