Dijkstra algorithm

Dijkstra algorithm-Single Source Shortest Path

1. Dijkstra’s Algorithm
An algorithm that is used for finding the shortest distance, or path, from starting node to target
node in a weighted graph is known as Dijkstra’s Algorithm.
Example 01:









Solution
Visited
Vertex
A B C D E F
A 0 ∞ ∞ ∞ ∞ ∞
F 14 9 ∞ ∞ 7
C 14 9 ∞ 22
B 11 ∞ 20
D 19 20
E 20

if(d(u) + c(u,v) < d(v))
then d(v) = d(u) + c(u,v)
Shortest path from A to E: A, C, E
Distance = 9 + 11 = 20






A
B D
C
F
E
14
8
6
15
7
9
10
11
2

2. Example 02:









Solution
Visited
Vertex
A B C D E F
A 0 ∞ ∞ ∞ ∞ ∞
B 2 5 ∞ ∞ 11
C 5 7 15 11
D 7 15 11
F 15 11
E 15

if(d(u) + c(u,v) < d(v))
then d(v) = d(u) + c(u,v)
Shortest path from A to E: A, B, E
Distance = 2 + 13 = 15

Dijkstra’s Algorithm Pseudocode
function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q

A
F D
B
C
E
11
17
1
12
5
2
8 13
5

3. distance[S] <- 0

while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]