Dijkstra’s Algorithm

1
 Single-Source Shortest Path Problem

Single-Source Shortest Path Problem - The

problem of finding shortest paths from a source
vertex v to all other vertices in the graph.
 Dijkstra's algorithm
Dijkstra's algorithm - is a solution to the single-source
shortest path problem in graph theory.

Works on both directed and undirected graphs. However,

all edges must have nonnegative weights.

Input: Weighted graph G={E,V} and source vertex v∈V,

such that all edge weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths

themselves) from a given source vertex v∈V to all other
vertices
 Approach
• The algorithm computes for each vertex u the distance to u
from the start vertex v, that is, the weight of a shortest path
between v and u.
• the algorithm keeps track of the set of vertices for which the
distance has been computed, called the cloud C
• Every vertex has a label D associated with it. For any vertex u,
D[u] stores an approximation of the distance between v and
u. The algorithm will update a D[u] value when it finds a
shorter path from v to u.
• When a vertex u is added to the cloud, its label D[u] is equal
to the actual (final) distance between the starting vertex v and
vertex u.
4
 Dijkstra′s algorithm (for single-source shortest
paths problem)
• Greedy approach. Maintain a set of explored nodes S for which
algorithm has determined d[u] = length of a shortest s↝u path.

・Initialize S  { s }, d[s]  0.
・Repeatedly choose unexplored node v  S which minimizes
d’(v) = min d[u] + l e
e = (u, v) : u S

add v to S, and set d[v]  d’(v).

 ℓe v
d[u]
u
S

6
7
 Example: Initialization

Distance(source) = 0 ∞ Distance (all vertices

0 A 2
B but source) = ∞

4 1 3 10

2 2 ∞
∞ C D E

5 8 ∞ 4 6

1
F G

∞ ∞

Pick vertex in List with minimum distance.

8
 Example: Update neighbors'
distance
0 2
2
A B

4 1 3 10

2 2 ∞
∞ C D E

5 8 1 4 6

Distance(B) = 2 1
F G
Distance(D) = 1
∞ ∞

9
Example: Remove vertex with
minimum distance
0 2
2
A B

4 1 3 10

2 2 ∞
∞ C D E

5 8 1 4 6

1
F G

∞ ∞

Pick vertex in List with minimum distance, i.e., D

10
 Example: Update neighbors

0 2
2
A B

4 1 3 10

2 2 3
3 C D E

5 8 1 4 6

Distance(C) = 1 + 2 = 3 1
F G
Distance(E) = 1 + 2 = 3
Distance(F) = 1 + 8 = 9 9 5
Distance(G) = 1 + 4 = 5

11
 Example: Continued...
Pick vertex in List with minimum distance (B) and update neighbors
0 2
2
A B

4 1 3 10

2 2 3
3 C D E

5 8 1 4 6
Note : distance(D) not
F 1
G updated since D is
already known and
9 5 distance(E) not updated
since it is larger than
previously computed

12
 Example: Continued...
Pick vertex List with minimum distance (E) and update neighbors

0 2
2
A B

4 1 3 10

2 2 3
3 C D E

5 8 1 4 6

1
F G
No updating
9 5

13
 Example: Continued...
Pick vertex List with minimum distance (C) and update neighbors

0 2
2
A B

4 1 3 10

2 2 3
3 C D E

5 8 1 4 6

Distance(F) = 3 + 5 = 8 1
F G

8 5

14
 Example: Continued...
Pick vertex List with minimum distance (G) and update neighbors

0 2
2
A B

4 1 3 10

2 2 3
3 C D E

5 8 1 4 6

1
F G
Previous distance
6 5
Distance(F) = min (8, 5+1) = 6

15
 Example (end)

0 2
2
A B

4 1 3 10

2 2 3
3 C D E

5 8 1 4 6

1
F G

6 5
Pick vertex not in S with lowest cost (F) and update neighbors

16
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
 Correctness :“Cloudy” Proof
When a vertex is added to the cloud, it has shortest
distance to source.

Least cost node v P: Next shortest path from

inside the known cloud

THE KNOWN
competitor v'
CLOUD
Source

• If the path to v is the next shortest path, the path to v' must be at
least as long. Therefore, any path through v' to v cannot be shorter!
 Dijkstra’s Correctness
• We will prove that whenever u is added to S, d[u] =
(s,u), i.e., that d[u] is minimum, and that equality is
maintained thereafter
• Proof
– Note that   v, d[v] ≥ (s,v)
– Let u be the first vertex picked such that there is a shorter
path than d[u], i.e., that d[u]  (s,u)
– We will show that this assumption leads to a contradiction

27
 Dijkstra Correctness (2)
• Let y be the first vertex  V – S on the actual shortest
path from s to u, then it must be that d[y] = (s,y)
because
– d[x] is set correctly for y's predecessor x  S on the shortest
path (by choice of u as the first vertex for which d is set
incorrectly)
– when the algorithm inserted x into S, it relaxed the edge
(x,y), assigning d[y] the correct value

28
 Dijkstra Correctness (3)

d [u ]  ( s , u ) (initial assumption)
= ( s , y ) + ( y , u ) (optimal substructure)
= d [ y ] + ( y , u ) (correctness of d [ y ])
 d[ y] (no negative weights)

• But if d[u] > d[y], the algorithm would have chosen y

(from the Q) to process next, not u −− Contradiction
• Thus d[u] = (s,u) at time of insertion of u into S, and
Dijkstra's algorithm is correct

29
 Dijkstra’s Pseudo Code
• Graph G, weight function w, root s

relaxing
edges

30
 Time Complexity: Using List
The simplest implementation of the Dijkstra's algorithm
stores vertices in an ordinary linked list or array
– Good for dense graphs (many edges)

• |V| vertices and |E| edges

• Initialization O(|V|)
• While loop O(|V|)
– Find and remove min distance vertices O(|V|)
• Potentially |E| updates
• Update costs O(1)

Total time O(|V2| + |E|) = O(|V2| )

Time Complexity: Priority Queue
For sparse graphs, (i.e. graphs with much less than |V2| edges)
Dijkstra's implemented more efficiently by priority queue

• Initialization O(|V|) using O(|V|) buildHeap

• While loop O(|V|)
• Find and remove min distance vertices O(log |V|) using O(log |V|)
deleteMin

• Potentially |E| updates

• Update costs O(log |V|) using decreaseKey

Total time O(|V|log|V| + |E|log|V|) = O(|E|log|V|)

• |V| = O(|E|) assuming a connected graph
32