# 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^{2}|).

Note:Dijkstra’s algorithm cannot handle negative weight

## Examples

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

- Draw a table showing the intermediate distance values of all the nodes at each iteration of the algorithm.
- 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