DIJIKTRAS ALGORITHM

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III:

DIJIKTRAS ALGORITHM - TRACY SNEHA
1of 23
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.

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 2 of 23
 Applications

- Maps (Map Quest, Google Maps)

- Routing Systems

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 3 of 23
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
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 4 of 23
 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.

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA
5 of 23
 NUMERICAL ALGORITHM

• FORMULAE
O(ǀVǀ2+ǀEǀ)=O(ǀVǀ2)

Where,
E = Edges
V = Vertices
ǀEǀ = Function of Edges
ǀVǀ = Function of Vertices
O = Constant.

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 6 of 23
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.

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 7 of 23
 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
∞ ∞

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 8 of 23
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

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 9 of 23
 Example: Update neighbors
0 2
2
A B

4 1 3 10

2 2
3 C D E 3

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

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 10 of 23
 Pick vertex in List with minimum distance (B) and update neighbors
0 2
2
A B

4 1 3 10

2 2
3 C D E 3

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

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 11 of 23
 Pick vertex List with minimum distance (E) and update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

1
F G
No updating
9 5

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 12 of 23
 Pick vertex List with minimum distance (C) and update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

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

8 5

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 13 of 23
 Pick vertex List with minimum distance (G) and update neighbors

0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

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

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 14 of 23
 0 2
2
A B

4 1 3 10

2 2
3 C D E 3

5 8 1 4 6

1
F G

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

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 15 of 23
Another Example

16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 16 of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 17 of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA
18of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 19 of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 20 of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA
21 of 23
 22of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 23of 23
16IT206 DATA STRUCTURES AND ALGORITHMS UNIT III: DIJIKTRAS ALGORITHM - TRACY SNEHA 24of 23