Dijkstra’s Algorithm | Shortest Path Algorithm

Dijkstra’s Algorithm-

 

  • Dijkstra’s Algorithm is one of the very famous greedy algorithms.
  • It is used for solving the single source shortest path problem which gives the shortest paths from one particular source node to all the other nodes of the given graph.

 

Conditions for Dijkstra’s Algorithm-

 

  1. Dijkstra’s algorithm works only for those graphs that are connected.
  2. Dijkstra’s algorithm works only for those graphs that do not contain any edges with negative weights.
  3. The actual Dijkstra’s algorithm does not output the shortest paths. It only provides the value or cost of the shortest paths.
  4. By making minor modifications in the actual algorithm, the shortest paths can be easily obtained.
  5. Dijkstra’s algorithm works for directed as well as undirected graphs.

 

Steps for Dijkstra’s Algorithm-

 

To apply Dijkstra’s Algorithm on any given graph, we will follow the following steps-

 

Step-01:

 

First of all, we will define two sets-

  1. One set will contain all those vertices which have been included in the shortest path tree (SPT). In the beginning, this set will be empty.
  2. Other set will contain all those vertices which are still left to be included in the shortest path tree (SPT). In the beginning, this set will contain all the vertices of the graph.

 

Step-02:

 

For each vertex of the graph, we will define two variables as-

  1. Π[v] which denotes the predecessor of vertex ‘v’
  2. d[v] which denotes the shortest path estimate of vertex ‘v’ from the source vertex.

 

Initially, we will set the value of these variables as-

 

  • Set the value of variable ‘Π’ for each vertex to NIL i.e. Π[v] = NIL
  • Set the value of variable ‘d’ for source vertex to 0 i.e. d[S] = 0
  • Set the value of variable ‘d’ for rest of the vertices to ∞ i.e. d[v] = ∞

 

Step-03:

 

We will keep repeating the following procedure until all the vertices of the graph will be processed-

  1. Among unprocessed  vertices, we will choose a vertex with the minimum value of variable ‘d’
  2. Then, we will relax its outgoing edges.
  3. After relaxing the edges for a vertex, we will update the sets created in step-01.

 

Meaning of Edge Relaxation-

 

Consider the edge (a,b) in the graph shown-

Here, d[a] and d[b] are shortest path estimates for vertices a and b respectively from source vertex ‘S’.

If d[a] + w < d[b]

then d[b] = d[a] + w and Π[b] = a

 

PRACTICE PROBLEM BASED ON DIJKSTRA’S ALGORITHM-

 

Problem-

 

Using Dijkstra’s Algorithm, find out the shortest distance from the source vertex ‘S’ to the rest of the vertices in the given graph.

Also, write the order in which all the vertices of the graph are visited.

 

 

Solution-

 

Step-01:

 

We will create the two sets as-

  • Unvisited set : {S , a , b , c , d , e}
  • Visited set     : { }

 

Step-02:

 

Now, we will create two variables  Π and d for each vertex and initialize them as-

  • Π[S] = Π[a] = Π[b] = Π[c] = Π[d] = Π[e] = NIL
  • d[S] = 0
  • d[a] = d[b] = d[c] = d[d] = d[e] = ∞

 

Step-03:

 

Now, we will choose vertex S and relax its outgoing edges because among unprocessed vertices, shortest path estimate for vertex ‘S’ is least.

 

Initially-

Now,

  • d[S] + 1 = 0 + 1 = 1 < ∞

∴ d[a] = 1 and Π[a] = S

  • d[S] + 5 = 0 + 5 = 5 < ∞

∴ d[b] = 5 and Π[b] = S

 

Now, Our SPT becomes-

 

Now, we update the sets as-

Unvisited set : {a , b , c , d , e}

Visited set : {S}

 

Step-04:

 

Now, we will choose vertex ‘a’ and relax its outgoing edges because among unprocessed vertices, shortest path estimate for vertex ‘a’ is least.

 

Initially-

 

 

Now,

  • d[a] + 2 = 1 + 2 = 3 < ∞

∴ d[c] = 3 and Π[c] = a

  • d[a] + 1 = 1 + 1 = 2 < ∞

∴ d[d] = 2 and Π[d] = a

  • d[b] + 2 = 1 + 2 = 3 < 5

∴ d[b] = 3 and Π[b] = a

 

Now, Our SPT becomes-

 

Now, we update the sets as-

Unvisited set : {b , c , d , e}

Visited set : {S , a}

 

Step-05:

 

Now, we will choose vertex ‘d’ and relax its outgoing edges because among unprocessed vertices, shortest path estimate for vertex ‘d’ is least.

 

Initially-

Now,

  • d[d] + 2 = 2 + 2 = 4 < ∞

∴ d[e] = 4 and Π[e] = d

 

Now, Our SPT becomes-

 

 

Now, we update the sets as-

Unvisited set : {b , c , e}

Visited set : {S , a , d}

 

Step-06:

 

Now, we will choose vertex ‘b’ and relax its outgoing edges. We can choose any of the vertices ‘b’ or ‘c’ because among unprocessed vertices, for both of them, shortest path estimate is least.

 

Initially-

Now,

  • d[b] + 2 = 3 + 2 = 5 > 2

∴ No change

So, Our SPT remains the same as in Step-04.

 

Now, we update the sets as-

Unvisited set : {c , e}

Visited set     : {S , a , d , b}

 

Step-07:

 

Now, we choose vertex ‘c’ and relax its outgoing edges because among unprocessed vertices, shortest path estimate for vertex ‘c’ is least.

 

Initially-

Now,

  • d[c] + 1 = 3 + 1 = 4 = 4

∴ No change

Now, Our SPT remains the same as in Step-04.

 

Now, we update the sets as-

Unvisited set : {e}

Visited set : {S , a , d , b , c}

 

Step-08:

 

Now, we choose vertex ‘e’ and relax its outgoing edges because it is the only remaining unprocessed vertex.

There are no outgoing edges for vertex ‘e’. So, Our SPT remains the same as in Step-04.

 

Now, we update the sets as-

Unvisited set : { }

Visited set : {S , a , d , b , c , e}

 

Now, All the vertices of the graph have been processed, so we are done.

Thus,

Our final Shortest Path Tree is as follows which represents the shortest paths from the source vertex ‘S’ to all other vertices of the given graph-

 

Shortest Path Tree (SPT)

 

The order in which all the vertices have been processed is- S , a , d , b , c , e

 

Dijkstra’s Algorithm-

 

dist[S] ← 0                                                   // We set the distance to source vertex as 0

Π[S] ← NIL                                                   // We set the predecessor of source vertex as NIL

for all v ∈ V – {S}                                          // For all other vertices

do dist[v] ← ∞                                       // We set all other distances to ∞

Π[v] ← NIL                                            // We set the predecessor of all other vertices as NIL

S ← ∅                                                          // The set of vertices that have been visited ‘S’ is initially empty

Q ← V                                                          // The queue ‘Q’ initially contains all the vertices

while Q ≠ ∅                                                  // While loop executes till the queue is not empty

do u ← mindistance (Q, dist)                // We select a vertex from Q with the least distance

← S ∪ {u}                                              // We add vertex ‘u’ to ‘S’ list of vertices that have been visited

for all v ∈ neighbors[u]                                 // For all the neighboring vertices of vertex ‘u’

do if dist[v] > dist[u] + w(u,v)                 // if any new shortest path is discovered

     then dist[v] ← dist[u] + w(u,v)          // We select the new value of the shortest path

return dist

 

Time Complexity Analysis of Dijkstra’s Algorithm-

 

Case-01: When the graph G is represented as an adjacency matrix and priority queue Q is represented as an unordered list-

 

  • A[i,j] stores the information about edge (i,j)
  • Time taken for selecting i with the smallest dist is O(V).
  • For each neighbor of i, time taken for updating dist[j] is O(1) and there will be maximum V neighbors.
  • Time taken for each iteration of the loop is O(V) and one vertex is deleted from Q.
  • Thus, total time complexity becomes O(V2)

 

Case-02: When graph G is represented as an adjacency list and priority queue Q is represented as a binary heap-

 

  • With adjacency list representation, we can traverse all the vertices of a graph using Breadth First Search in O(V+E) time.
  • In min heap, operations like extract-min and decrease-key value takes O(logV) time.
  • So, overall time complexity is O(E+V) x O(logV) which is O((E + V) x logV) = O(ElogV)
  • Time Complexity can be reduced to O(E+VlogV) using Fibonacci heap.

 

To gain better understanding of the concepts of Dijkstra’s Algorithm,

Watch this Video lecture

 

Download the handwritten notes of “Dijkstra Algorithm” here-

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Dijkstra's Algorithm | Shortest Path Algorithm
Article Name
Dijkstra's Algorithm | Shortest Path Algorithm
Description
Dijkstra's Algorithm is a greedy algorithm for solving single source shortest path problem that provides us with the shortest path from one particular source node to all other nodes in the given graph.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-