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)
Weight updating in Dijkstra’s algorithm

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

Dijkstra’s Algorithm example
  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 uABCDEFGH
dist[u]0
π[u]NILNILNILNILNILNILNILNIL

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 uABCDEFGH
dist[u]0148
π[u]NILANILNILAANILNIL

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 uABCDEFGH
dist[u]013477
π[u]NILABNILABBNIL

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 uABCDEFGH
dist[u]0134475
π[u]NILABCABCNIL

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 uABCDEFGH
dist[u]0134475
π[u]NILABCABCNIL

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 uABCDEFGH
dist[u]01344758
π [u]NILABCABDD

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 uABCDEFGH
dist[u]01344656
π [u]NILABCAGCG

Iteration 7:

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

Adjacent[F] = { }

So, no change in table

Vertex uABCDEFGH
dist[u]01344656
p[u]NILABCAGCG

Iteration 8:   

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

Adjacent[H] = { }

So, no change in table

Vertex uABCDEFGH
dist[u]01344656
p[u]NILABCAGCG

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

example of Dijkstra’s 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 :


Additional Reading: Read More

You may also like...

Leave a Reply

Your email address will not be published.