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.

d(S, N) = 11 d(S, C) + d(C, N) < d(S, N) ⇒ Relax edge (S, N) Update d(S, N) = 8	d(S, N) = 7 d(S, C) + d(C, N) > d(S, N) ⇒ Don’t update d(S, N)

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(|V²|).

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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	∞	∞	∞	∞	∞	∞	∞
π[u]	NIL	NIL	NIL	NIL	NIL	NIL	NIL	NIL

Iteration 1:

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

Adjacent[A] = {B, E, F}

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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	∞	∞	4	8	∞	∞
π[u]	NIL	A	NIL	NIL	A	A	NIL	NIL

Iteration 2:

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

Adjacent[B] = {C, F, G}

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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	∞	4	7	7	∞
π[u]	NIL	A	B	NIL	A	B	B	NIL

Iteration 3:

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

Adjacent [C] = {D, G}

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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	4	4	7	5	∞
π[u]	NIL	A	B	C	A	B	C	NIL

Iteration 4:

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

Adjacent[E] = {F}

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

= 4 + 5

= 9

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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	4	4	7	5	∞
π[u]	NIL	A	B	C	A	B	C	NIL

Iteration 5:

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

Adjacent[D] = {G, H}

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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	4	4	7	5	8
π [u]	NIL	A	B	C	A	B	D	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

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	4	4	6	5	6
π [u]	NIL	A	B	C	A	G	C	G

Iteration 7:

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

Adjacent[F] = { }

So, no change in table

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	4	4	6	5	6
p[u]	NIL	A	B	C	A	G	C	G

Iteration 8:   

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

Adjacent[H] = { }

So, no change in table

Vertex u	A	B	C	D	E	F	G	H
dist[u]	0	1	3	4	4	6	5	6
p[u]	NIL	A	B	C	A	G	C	G

We can easily derive the shortest path tree for given graph from above table. In the table, p[u] indicates the parent node of vertex u. The shortest path tree is shown in following figure

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

• Binary Knapsack Problem
• Fractional Knapsack Problem
• Job Scheduling Problem
• Activity Selection Problem
• Huffman Coding
• Optimal Storage on Tapes
• Optimal Merge Pattern
• Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm

---

Additional Reading: Read More