# Dijkstra’s Algorithm – Single Source Shortest Path Algorithm

Dijkstra’s Algorithm is also known as Single Source Shortest Path (SSSP) problem. It is used to find the shortest path from source node to destination node in graph.

The graph is widely accepted data structure to represent distance map. The distance between cities effectively represented using graph.

• Dijkstra proposed an efficient way to find the single source shortest path from the weighted graph. For a given source vertex s, the algorithm finds the shortest path to every other vertex v in the graph.
• Assumption : Weight of all edges is non-negative.
• Steps of the Dijkstra’s algorithm are explained here:

1.     Initializes the distance of source vertex to zero and remaining all other vertices to infinity.

2.     Set source node to current node and put remaining all nodes in the list of unvisited vertex list. Compute the tentative distance of all immediate neighbour vertex of the current node.

3.     If the newly computed value is smaller than the old value, then update it.

For example, C is the current node, whose distance from source S is dist (S, C) = 5.

• Consider N is the neighbour of C and weight of edge
(C, N) is 3. So the distance of N from source via C would be 8.
• If the distance of N from source was already computed and if it is greater than 8 then relax edge (S, N) and update it to 8, otherwise don’t update it.

4.     When all the neighbours of a current node are explored, mark it as visited. Remove it from unvisited vertex list. Mark the vertex from unvisited vertex list with minimum distance and repeat the procedure.

5.     Stop when the destination node is tested or when unvisited vertex list becomes empty.

## Algorithm for Dijkstra’s Algorithm

Dijkstra’s shortest path algorithm is described below :

Algorithm DIJAKSTRA_SHORTEST_PATH(G, s, t)
// s is the source vertex
// t is the target vertex
// π[u] stores the parent / previous node of u
// V is the set of vertices in graph G

dist[s] ← 0
π[s] ← NIL

for each vertex v ∈ V do
if v ≠ s then
dist[v] ← ∞
π[v] ← undefined
end
ENQUEUE(v, Q)		// insert v to queue Q
end

while Q is not empty do
u ← vertex in Q having minimum dist[u]
if u == t then
break
end
DEQUEUE(u, Q)	  // Remove u from queue Q

for each adjacent node v of u do
val ← dist[u] + weight(u, v)
if val<dist[v] then
dist[v] ← val
π[v] ← u
end
end
end

## Complexity analysis of Dijkstra’s Algorithm

First for loop does initialization in O(|V|) time. As there are |V| nodes in the graph, size of queue Q would be V, and hence while loop iterates |V| times in worst case. For loop inside while loop run maximum |V| time, because a node can have maximum |V| – 1 neighbours. The worst case upper bound running time of this algorithm is described as O(|V2|).

Note: Dijkstra’s algorithm cannot handle negative weight

## Examples

Problem: Suppose Dijkstra’s algorithm is run on the following graph, starting at node A

1. Draw a table showing the intermediate distance values of all the nodes at each iteration of the algorithm.
2. Show the final shortest path tree.

Solution:

Here, source vertex is A.

dist[u] indicates distance of vertex u from source

π[u] indicates parent / previous node of u

Initialization:

dist[source] = 0 ⇒ dist[A] = 0

π[source] = undefined ⇒ π[A] = NIL

dist[B] = dist[C] = dist[D] = dist[E] = dist [F] = dist[G]= dist[H] = ∞

π[B] = π[C] = π[D] = π[E] = π[F] = π[G] = π[H]= NIL

Iteration 1:

u = unprocessed vertex in Q having minimum dist[u] = A

val[B] = dist[A] + weight(A, B)

= 0 + 1

= 1

Here, val[B] <dist[B], so update dist[B]

dist[B] = 1, and π[B] = A

val[E] = dist[A] + weight(A, E)

= 0 + 4

= 4

Here, val[E] < dist[E], so update dist[E]

dist[E] = 4 and π[6] = A

val[F] = dist[A] + weight(A, F)

= 0 + 8

= 8

Here, val[F] < dist[F], so update dist[F]

dist[F] = 8 and π[F] = A

Iteration 2:

u =  unprocessed vertex in Q having minimum dist[u] = B

val[C] = dist[B] + weight(B, C)

= 1 + 2

= 3

Here, val[C] < dist[C], so update dist[C]

dist[C] = 3 and π[C] = B

val[F] = dist[B] + weight(B, F)

= 1 + 6

= 7

Here, val[F] < dist[F], so update dist[F]

dist[F] = 7 and π[F] = B

val[G] = dist[B] + weight(B, G)

= 1 + 6

= 7

Here, val[G] < dist[G], so update dist[G]

dist[G] = 7 and π[G] = B

Iteration 3:

u = unprocessed vertex in Q having minimum dist[u] = C

val[D] = dist[C] + weight(C, D)

= 3 + 1

= 4

Here, val[D] < dist[D], so update dist[D]

dist[D] = 4 and π[D] = C

val[G] = dist[C] + weight(C, G)

= 3 + 2

= 5

Here, val[G] < dist[G], so update dist[G]

dist[G] = 5 and π[G] = C

Iteration 4:

u = unprocessed vertex in Q having minimum dist[u] = E

val[F] = dist[E] + weight(E, F)

= 4 + 5

= 9

Here, val[F] > dist[F], so no change in table

Iteration 5:

u = unprocessed vertex in Q having minimum dist[u] = D

val[G] = dist[D] + weight(D, G)

= 4 + 1

= 5

Here, val[G] = dist[G], so don’t update dist[G]

val[H] = dist[D] + weight(D, H)

= 4 + 4

= 8

Here, val[H] < dist[H], so update dist[H]

dist[H] = 8 and π[H] = D

Iteration 6:

u = unprocessed vertex in Q having minimum dist[u] = G

Adjacent[G] = { F, H }

val[F] = dist[G] + weight(G, F)

= 5 + 1

= 6

Here, val[F] < dist[F], so update dist[F]

dist[F] = 6 and π[F] = G

val[H] = dist[G] + weight(G, H)

= 5 + 1

= 6

Here, val[H] < dist[H], so update dist[H]

dist[H] = 6 and π[H] = G

Iteration 7:

u = unprocessed vertex in Q having minimum dist[u] = F

So, no change in table

Iteration 8:

u = unprocessed vertex in Q having minimum dist[u] = H