Dijkstra's Algorithm

Dijkstra's algorithm is a greedy algorithm for the shortest path from a single vertex. It grows a spanning tree in the graph always adding the edge that connects the start vertex with a minimal path length to the spanning tree.

Dijkstra's algorithm uses a priority queue of vertices key by the distance estimation.

The distances from the start vertex are update by a relaxation process. The distances are over estimate and as new information is gain the estimates are improved from above.

if d[u*] + w(u*, u) < d[u] then

d[u] ← d[u*] + w(u*, u)

I assume that you have already seen the algorithm, so I'll jump to the author's pseudo code.

Algorithm Dijkstra(G, s)

// Returns the distance from the start vertex, s,

// and the array of penultimate, p[v] of the path to the vertex, v

initialize(Q) // priority queue of vertices

for each vertex v in V do

d[v] ← ∞

insert(Q, v, d[v])

d[s] ← 0

decrease(Q, s, d[s]) // this update in the priority queue

V_T ← {} // empty set

for i ← 0 to |V|-1 do

u* ← deleteMin(Q)

V_T ← V_T union {u*}

for every vertex, u, adjacent to u* and in V-VT do

if d[u*] + w(u*, u) < d[u] then

p[u] ← u*

d[u] ← d[u*] + w(u*, u)

decrease(Q, u, d[u])

Illustrate

The cost depends on the implementation of the priority queue and the graph.

Note the loop over adjacent runs the degree of the vertex. The outer loop runs |V| so the number of checks for the relaxation and priority queue updates is |E|.

The total cost is the sum of the cost to make the priority queue, the cost of the remove minimum and the cost for all the updates. If unsorted priority queue is used then the cost is dominated by the cost of all the remove minimum, Θ(|V|²). If an heap is used the cost is both the updates and removes from the priority queue Θ((|V| + |E|) lg |V|)

A dense graph should use adjacency matrix and unsorted priority queue then the total cost is Θ(|V|²). A sparse graph should use an adjacency list and a heap then the total cost is Θ(|E| lg |V|) for a connected graph.