Dijkstra Algorithm

Difficulty Level Medium
Frequently asked in Accolite Adobe Amazon Cisco Interactive Solutions Morgan Stanley Samsung Vizury
Dijkstra Algorithm Graph Greedy Shortest Path TheoryViews 2632

Dijkstra is the shortest path algorithm. Dijkstra algorithm is used to find the shortest distance of all nodes from the given start node. It logically creates the shortest path tree from a single source node, by keep adding the nodes greedily such that at every point each node in the tree has a minimum distance from the given start node.

Dijkstra algorithm is a greedy approach that uses a very simple mathematical fact to choose a node at each step.

“Adding two positive numbers will always results in a number greater than both inputs”.

Algorithm

Here is the Dijkstra algorithm

Variables used

  1. n: number of nodes.
  2. e: number of edges.
  3. visited, an array of size n to keep track of nodes that are added in the tree.
  4. cost, an array of size n to store the minimum cost to reach the ith node from start node via a valid path in the tree.

Steps

  1. Initialize visited array with false which shows that currently, the tree is empty.
  2. Initialize cost array with infinity which shows that it is impossible to reach any node from the start node via a valid path in the tree.
  3. The cost to reach the start node will always be zero, hence cost[start]=0.
  4. Now at every iteration we choose a node to add in the tree, hence we need n iterations to add n nodes in the tree:
    • Choose a node that has a minimum cost and is also currently non-visited i.e., not present in the tree.
    • Update the cost of non-visited nodes which are adjacent to the newly added node with the minimum of the previous and new path.
    • Mark the node as visited.

Example of Dijkstra Algorithm

Given a graph, compute the minimum distance of all nodes from A as a start node.

dijkstra algorithm

Step by Step Solution of Dijkstra Algorithm

dijkstra algorithm
1. Distance of A from A is 0

 

dijkstra algorithm
2. Distance of C from A is 1

 

dijkstra algorithm
3. Distance of D from A is 3

 

4. Distance of B from A is 3

 

5. Distance of E from A is 7

Disadvantage of Dijkstra Algorithm

As we know the basic property used in Dijkstra is the addition of two positive numbers, hence, this algorithm may lead to the wrong answer in the case of the graph containing negative edges.

Example

Consider the graph

Starting node: A

Dijkstra will compute 3 as minimum distance to reach B from A.

But we can clearly see A->C->E->B  path will cost 2 to reach B from A.

Question on Dijkstra Algorithm

Given a directed weighted graph with n nodes and e edges, your task is to find the minimum cost to reach each node from the given start node

Input

The first line of input contains two integer n (number of edges) and e (number of edges).

The next e lines contain three space-separated integers u, v and w where:

  • u: source node
  • v: destination node
  • w: weight of the edge

The last line contains s, denoting start node

Constraints

1<=n<=1000

0<=e<=(n*(n-1))/2

1<=weight<=103

The graph contains no self-loop and multiple edges.

C++ Code for Dijkstra Algorithm

#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;

// Function to find the non-visited node which is at minimum distance
int findMin(int n,int cost[],bool visited[]){
    int min=INF;
    int node=0;
    for(int i=0;i<n;i++){
        if(visited[i]==false && min>cost[i]){
            min=cost[i];
            node=i;
        }
    }
    return node;
}
void dijkstra(int n, vector<pair<int,int>> graph[], int start){
    bool visited[n];    // to specify which nodes are yet to visit
    int cost[n];            // cost[i] specifies the minimum cost to reach ith node from start node through visited nodes
    for(int i=0;i<n;i++){
        cost[i]=INF;                          // initialize cost array with INFINITY
                                             // to signify that all nodes are non-reachable initially
        visited[i]=false;                     // initialize visited array with false 
                                             // to signify that all nodes are non-visited initially
    }
    
    cost[start]=0;                           // minimum cost to reach the start node will be zero
    int count=0;                             // count will keep track of how many nodes are visited till now
    
    while(count<n){
        int node = findMin(n,cost,visited);
        visited[node]=true;
        for(auto &i:graph[node]){
            if(visited[i.first]==false){
                cost[i.first]=min(cost[i.first],cost[node]+(i.second));
            }
        }
        count++;
    }
    
    for(int i=0;i<n;i++){
        cout<<"Distance of node "<<i<<" from node "<<start<<" is "<<cost[i]<<"\n";
    }
}
int main(){
    int n,e;
    cin>>n>>e;
    vector<pair<int,int>> graph[n];
    for(int i=0;i<e;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back(make_pair(v,w));
        graph[v].push_back(make_pair(u,w));
    }
    int start;
    cin>>start;
    dijkstra(n,graph,start);
}
5 7
0 2 5
0 1 3
2 3 2
3 4 5
2 4 1
4 1 4
2 3 7
0
Distance of node 0 from node 0 is 0
Distance of node 1 from node 0 is 3
Distance of node 2 from node 0 is 5
Distance of node 3 from node 0 is 7
Distance of node 4 from node 0 is 6

Java Code for Dijkstra Algorithm

import java.util.Scanner;


public class Main {
  public static int [][] graph;
  public static int [] visited;
  public static int [] cost;
  public static int start;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n,e, INF = Integer.MAX_VALUE;
      n = sc.nextInt();
      e = sc.nextInt();
      
      graph = new int [n][n];
      visited = new int [n];
      cost = new int[n];
        
      for (int i = 0; i < n; i++) {			
        for (int j = 0; j < n; j++) {
          graph[i][j] = -1;
        }
      }
      
      for (int i = 0; i < e; i++) {
        int u = sc.nextInt();
        int v = sc.nextInt();
        int w = sc.nextInt();
        graph[u][v] = w;
        graph[v][u] = w;
      }
      
      start = sc.nextInt();
      
      for (int i = 0; i < n; i++) {
        cost[i]=INF;
      }
      cost[start]=0;
      
      dijkstra(start);
      printResult();
    }
  
  /* Recursive function to find the minimum distance of each node from given start node*/
  public static void dijkstra(int start){
    for (int i = 0; i <cost.length; i++) {
      if (graph[start][i] > -1 && cost[i] > (graph[start][i] + cost[start]) ){
        cost[i] = graph[start][i] + cost[start];
      }
    }
    
    int j = minDist();
    if (j  == -1 )
      return;
    
    visited[j] = 1;
    dijkstra(j);		
  }
  
  /* Function to print the distance of each node from given start node*/
  public static void printResult(){
    for (int i = 0; i <cost.length; i++) {
    		System.out.println("Distance of node "+i+" from node "+start+" is "+cost[i]);
    }
  }
  
  /* Function to find non-visited node with minimum distance*/
  public static int minDist(){
    int minDistance = Integer.MAX_VALUE;
    int index = -1; 
    for (int i=0; i<cost.length; i++){
      if (minDistance>cost[i] && visited[i] == 0){
        minDistance = cost[i];
        index = i;				
      }
    }
    return index;
  }

}
Input:
4 5
0 1 12
0 3 24
2 0 3
1 3 10
3 2 12
0
Output:
Distance of node 0 from node 0 is 0
Distance of node 1 from node 0 is 12
Distance of node 2 from node 0 is 3
Distance of node 3 from node 0 is 15

Time complexity: O(n*n)

The time complexity of Dijkstra algorithm can be improved using binary heap to choose the node with minimum cost (step 4)

Reference

Go through more interview questions

Translate »