Given a network $G=(N,A)$ with arc lengths (or arc cost) $c_{ij}$ for each arc $(i,j)\in A$, we seek the shortest path from a source node $s$ to every node $i\in N$. That is, the paths $P_i$ from $s$ to each $i\in N$ with the smallest length

$$\sum _{(k,j)\in P_i}{c}_{kj}.$$

We let $A(i)$ be the arc adjacency list of node $i$ and define $C=\max \{c_{ij}:(i,j)\in A\}$.

As a min-cost flow problem, you can view this as sending 1 unit of flow throughout the network as cheaply as possible. This results in the following optimization problem:

$$\begin{array}{rlr}& \text{minimize}& \sum _{(i,j)\in A}{c}_{ij}{x}_{ij}\\ & \text{subject to}& \sum _{(i,j)\in A}{x}_{ij}-\sum _{(j,i)\in A}{x}_{ji}=\{\begin{array}{ll}n-1& \text{if }i=s\\ -1& \text{if }i\ne s\end{array}\\ & & x_{ij}\ge 0,\forall (i,j)\in A\end{array}$$

We make the following assumptions:

1. All arc lengths are integers.
2. The network contains a directed path from node $s$ to every other node in the network.
3. The network does not contain a negative cycle.
4. The network is directed.

Dijkstra’s Algorithm

Under the assumption that all arcs have non-negative arc lengths, Dijkstra’s algorithm finds the shortest paths from the source node $s$ to all other nodes in $\Theta (n^2)$ time.

Dijkstra’s algorithm maintains a label $d(i)$ which is an upper bound on the shortest path length from $s$ to node $i$. Nodes are either permanently labeled or temporarily labeled. The idea of the algorithm is to walk through the network and permanently label nodes in the order of their distances from $s$.

We start by setting $d(s)=0$ and every other node $j$ a temporary label of $d(j)=+\infty$. At each iteration, we pick the node $i$ with the smallest $d(i)$, make it permanent, and scan arcs in $A(i)$ to update the temporary labels of adjacent nodes.

We maintain an array $\text{pred}(i)$ which gives defines an out-tree $T$ rooted at the source node $s$. Every tree arc $(i,j)\in T$ satisfies the condition $d(j)=d(i)+c_{ij}$.

Algorithm 2 Dijkstra's shortest path algorithm

procedure Dijkstra($G=(N,A),~s$)

$S:=\emptyset$

$\overline{S} := N$

$d(i):=+\infty$ for all $i\in N$

$d(s):=0$

$\textup{pred}(s) := 0$

while $|S|<n$ do

let $i\in\overline{S}$ be a node for which $d(i)=\min\{d(j):j\in\overline{S}\}$

$S:=S\cup\{i\}$

$\overline{S}:=\overline{S}\setminus\{i\}$

for all $(i,j)\in A(i)$ do

if $d(j) > d(i)+c_{ij}$ then

$d(j) := d(i) + c_{ij}$

$\textup{pred}(j) := i$

end if

end for

end while

end procedure

Fibonacci Heap Implementation

If we make use of a Fibonacci heap $H=[0,\infty ]\times N$ where the keys are the distance labels and the values are the nodes, then we can pick the temporarily node with minimum distance label in $O(1)$ time. The new algorithm is given below:

Algorithm 3 Dijkstra's shortest path algorithm via a heap

procedure HeapDijkstra($G=(N,A),~s$)

create heap $H$

$d(i):=+\infty$ for all $i\in N$

$d(s):=0$

$\textup{pred}(s) := 0$

$H[0] = s$

while $H\ne\emptyset$ do

take the node $i$ from $H$ with minimum key

delete node $i$ from $H$

for all $(i,j)\in A(i)$ do

if $d(j) > d(i)+c_{ij}$ then

$d(j) := d(i) + c_{ij}$

$\textup{pred}(j) := i$

set key for node $j$ in $H$ to $d(j)$

end if

end for

end while

end procedure

The modified version runs in $\Theta (m+n\log n)$ time.