# Dijkstra

## Contents

## General information

**Algorithmic problem:** Single source shortest paths

**Prerequisities:** For all [math]a\in A[/math], it is [math]l(a) \geq 0[/math].

**Type of algortihm:** loop

**Auxiliary data:**

- A temporary
**distance value**[math]\delta(v) \in \mathbb{R}[/math] for each node [math]v \in V[/math]. At termination, it is [math]\delta(v) = \Delta(v)[/math] for all [math]v \in V[/math] where [math]\Delta(v)[/math] is the shortest [math](s,v)[/math]-path. - A bounded priority queue [math]Q[/math] of size [math]|V|-1[/math], which contains nodes from [math]V[/math] and takes their [math]\delta[/math]-values as keys. The node with minimal key is returned.

## Abstract view

**Invariant:** After [math]i \geq 0[/math] iterations:

- [math]Q[/math] contains all nodes of [math]V[/math] except [math]s[/math] and [math]i[/math] further nodes.
- For the nodes [math]v \in V[/math] not in [math]Q[/math], it is [math]\delta(v) = \Delta(v)[/math].
- For the nodes [math]v \in V[/math] in [math]Q[/math], [math]\delta(v)[/math] is the length of a shortest [math](s,v)[/math]-path that solely contains nodes not in [math]Q[/math] (except for [math]v[/math] itself, of course). As usual, this means [math]\delta(v) = +\infty[/math] if there is no such path.

In particular, it is [math]\delta(v) \geq \Delta(v)[/math] for each node [math]v \in V[/math].

**Variant:** [math]i[/math] increases by [math]1[/math].

**Break condition:**

- [math]Q = \emptyset[/math], which means that all nodes are reachable from [math]s[/math] and have been processed;
- otherwise, if [math]\delta(v) = +\infty[/math] for the next node [math]v[/math] of [math]Q[/math], which means that [math]\delta(v) = + \infty[/math] for
**every**node in [math]Q[/math] and hence none of the nodes in [math]Q[/math] is reachable from [math]s[/math].

## Induction basis

### Abstract view:

- All nodes of [math]V[/math] except [math]s[/math] have to be members of [math]Q[/math].
- Root [math]s[/math] must have correct distance [math]\Delta(s) = 0[/math].
- The other nodes must meet Invariant #3.

### Implementation:

- [math]\delta(s) := 0[/math];
- For all [math]a = (s,v) \in A[/math], set [math]\delta(v) := l(a)[/math].
- For all [math]v \in V\setminus\{s\}[/math] with [math](s,v) \notin A[/math] set [math]\delta(v) := +\infty[/math].
- Insert all nodes in [math]V\setminus\{s\}[/math] into [math]Q[/math].

### Proof:

Obvious.

## Induction step

### Abstract view:

One node is extracted from [math]Q[/math], and the distance values of the endnodes of its outgoing arcs are updated to meet Invariant #3.

### Implementation:

- Extract the next node [math]v[/math] from [math]Q[/math].
- For each outgoing arc [math]a = (v,w) \in A[/math] such that [math]w \in Q[/math], set [math]\delta(w) := min\{\delta(w), \delta(v) + l(a)\}[/math].

### Correctness:

The first invariant is trivially maintained. So we will focus on the second and third invariants.

Consider the moment immediately before the [math]i[/math]-iteration. The core of the proof is to show that [math]\delta(v) = \Delta(v)[/math] hold at that moment (and hence forever). For a contradiction, suppose there is an [math](s,v)[/math]-path [math]p[/math] whose length is strictly less than [math]\delta(v)[/math]. The third invariant implies that [math]p[/math] has nodes in [math]Q[/math] beside [math]v[/math]. Let [math]u[/math] denote the first such node on [math]p[/math]. Then none of the nodes on the subpath of [math]p[/math] from [math]s[/math] to [math]u[/math] belonged to [math]Q[/math] at that moment (except for [math]u[/math] itself, of course). Due to the [[prefix property, this subpath is a shortest [math](s,u)[/math]-path, so Invariant #3 implies [math]\delta(u) = \Delta(u)[/math]. On the other hand, the specific choice of [math]v[/math] implies [math]\delta(u) \geq \delta(v)[/math]. In summary, the subpath of [math]p[/math] from [math]s[/math] to [math]u[/math] is not shorter than [math]\delta(v)[/math]. To obtain [math]l(p) \lt \delta(v)[/math], the subpath of [math]p[/math] from [math]u[/math] to [math]v[/math] must have negative total length, which contradicts the prerequisite [math]l \geq 0[/math].

Now we know [math]\delta(v) = \Delta(v)[/math]. Therefore, [math]v[/math] fulfills the statement of the second invariant after the [math]i[/math]-th iteration. Of course, the second invariant is not violated by any other node either, and is thus maintained.

For a node [math]w \in V[/math] let [math]P_i (w)[/math] denote the set of all [math](s,w)[/math]-paths such that no node (except for [math]w[/math] itself) is in [math]Q[/math] immediately after the [math]i[/math]-th iteration. In particular, the statement of the third invariant means that [math]\delta(w)[/math] is the length of a shortest path in [math]P_i (w)[/math]. The induction hypothesis says that [math]\delta(w)[/math] is the minimum length of all [math](s,w)[/math]-paths in [math]P_{i-1} (w)[/math]. The difference [math]P_i (w) \setminus P_{i-1} (w)[/math] consists of all [math](s,w)[/math]-paths such that [math](v,w)[/math] is the last arc and all nodes except for [math]v[/math] and [math]w[/math] were not in [math]Q[/math] anymore immediately before the current iteration. Therefore, the second step of the iteration incorporates [math]P_i (w) \setminus P_{i-1} (w)[/math] in the computation of [math]\delta(w)[/math] appropriately to maintain Invaraint #3.

## Complexity

**Statement:** The worst-case complexity is in [math]O(T(n)\cdot(n+m))[/math], where [math]n = |V|[/math] and [math]m = |A|[/math], and [math]T(n)[/math] is the worst-case complexity for extraction/inserting nodes in [math]Q[/math].

**Proof:** Each node is inserted in and extracted from [math]Q[/math] at most once, respectively, which gives [math]O(T(n) \cdot n)[/math] in total. Also, each arc [math](v,w) \in A[/math] is touched at most once, namely

- in the initialization if [math]v = s[/math],
- when [math]v[/math] is extracted from [math]Q[/math] otherwise.

Therefore, all decrease-key operations require [math]O(T(n) \cdot m)[/math] in total.

## Heuristic speed-up techniques

- We do not need to insert all nodes except for [math]s[/math] in [math]Q[/math]. In fact, it suffices to initially insert the endnodes of the outgoing arcs of [math]s[/math] and, during an iteration, to insert the nodes of the outgoing arcs of the node that is being extracted from [math]Q[/math]. In a sense, the nodes of [math]Q[/math] then constitute the "frontierline" of the algorithm. We choose another variant on Dijkstra's algorithm mainly for simplicity of presentation.
- Clearly, Dijkstra's algorithm also solves the single-source single-target case. In this case, Dijkstra may safely terminate once [math]t[/math] has been extracted from [math]Q[/math]. In fact, the loop invariant implies [math]\delta(t) = \Delta(t)[/math] from then on. This variant on Dijkstra's algorithm is sometimes called the
**early termination variant**. - In the single-source single-target case, two searches may be applied simultaneously: one from [math]s[/math] on [math]G[/math], the other one from [math]t[/math] on the transpose of [math]G[/math]. This variant is called
**bidirectional search**. It terminates once one node has been seen by both searches. Then either the concatenation of the paths to this node from both searches is a shortest [math](s,t)[/math]-path, or such a path may be found among the paths of the following kind: There is an arc [math](v,w)\in A[/math] such that [math]v[/math] has been seen in the forward search from the source and [math]w[/math] has been seen in the backward search from [math]t[/math]. - In a scenario where we perform a large number of searches on the same graph and arc lengths, we do not need to touch the whole graph in each search:
- We change the algorithm as suggested by the first point: only keep the "frontierline" in [math]Q[/math].
- We also change the algorithm as suggested by the second point: terminate once [math]t[/math] is processed.
- To avoid touching all nodes for initializing the [math]\delta[/math]-values, we maintain sort of a
**version counter**, or**time stamp**, for each node, which holds the ID of the last search that met this node. Whenever a node is met in a search and the nodes version counter does not equal the ID of the current search, the distance value of this node is regarded as [math]+ \infty[/math] (no matter what its current value is).

- The early termination variant may be modified as follows: For admissible node potentials [math]h:V \to \mathbb{R}[/math], replace length [math]\ell[/math] by [math]\ell_h[/math] where [math]\ell_h(a) := \ell(a) + h(w) - h(v)[/math] for each [math]a = (v,w) \in A[/math]. This variant is usually called
**goal-directed search**. The heuristic idea is that we (hopefully) reach [math] t[/math] earlier because the arcs that roughly point towards [math]t[/math] are shortened, and the arcs the roughly point in a direction away from [math]t[/math] are lengthened.