Dijkstra Algorithm

Dijkstra Algorithm

 

Dijkstra algorithm is a single source shortest path algorithm and  single-source means their only one source is given and find the shortest path from the source to all the nodes.

 

 

Example of Dijkstra’s algorithm

Consider the following figure

 

Dijkstra Algorithm
Start with a weighted graph
Dijkstra Algorithm
Choose a begining vertex and assign infinity path values to all other devices
Dijkstra Algorithm
Go to every vertex and update its path length
Dijkstra Algorithm
If the length of path of the adjacent vertex is lesser than new path length then don’t update it
Dijkstra Algorithm

Avoid the updating path lengths of already visited vertices
Dijkstra Algorithm

After each iteration, we pick the not visited vertex with the least path length. So we have to choose 5 before 7
Dijkstra Algorithm

Now, notice how the rightmost vertex has its path length updated two times.
Dijkstra Algorithm
Repeat thw steps until all the vertices have been visited

 

 

Program of dijkstra’s Algorithm

#include <stdio.h>
#define INFINITY 9999
#define MAX 10

void Dijkstra(int Graph[MAX][MAX], int n, int start);

void Dijkstra(int Graph[MAX][MAX], int n, int start) {
  int cost[MAX][MAX], distance[MAX], pred[MAX];
  int visited[MAX], count, mindistance, nextnode, i, j;

  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (Graph[i][j] == 0)
        cost[i][j] = INFINITY;
      else
        cost[i][j] = Graph[i][j];

  for (i = 0; i < n; i++) {
    distance[i] = cost[start][i];
    pred[i] = start;
    visited[i] = 0;
  }

  distance[start] = 0;
  visited[start] = 1;
  count = 1;

  while (count < n - 1) {
    mindistance = INFINITY;

    for (i = 0; i < n; i++)
      if (distance[i] < mindistance && !visited[i]) {
        mindistance = distance[i];
        nextnode = i;
      }

    visited[nextnode] = 1;
    for (i = 0; i < n; i++)
      if (!visited[i])
        if (mindistance + cost[nextnode][i] < distance[i]) {
          distance[i] = mindistance + cost[nextnode][i];
          pred[i] = nextnode;
        }
    count++;
  }

  for (i = 0; i < n; i++)
    if (i != start) {
      printf("\nDistance from source to %d: %d", i, distance[i]);
    }
}
int main() {
  int Graph[MAX][MAX], i, j, n, u;
  n = 7;

  Graph[0][0] = 0;
  Graph[0][1] = 0;
  Graph[0][2] = 1;
  Graph[0][3] = 2;
  Graph[0][4] = 0;
  Graph[0][5] = 0;
  Graph[0][6] = 0;

  Graph[1][0] = 0;
  Graph[1][1] = 0;
  Graph[1][2] = 2;
  Graph[1][3] = 0;
  Graph[1][4] = 0;
  Graph[1][5] = 3;
  Graph[1][6] = 0;

  Graph[2][0] = 1;
  Graph[2][1] = 2;
  Graph[2][2] = 0;
  Graph[2][3] = 1;
  Graph[2][4] = 3;
  Graph[2][5] = 0;
  Graph[2][6] = 0;

  Graph[3][0] = 2;
  Graph[3][1] = 0;
  Graph[3][2] = 1;
  Graph[3][3] = 0;
  Graph[3][4] = 0;
  Graph[3][5] = 0;
  Graph[3][6] = 1;

  Graph[4][0] = 0;
  Graph[4][1] = 0;
  Graph[4][2] = 3;
  Graph[4][3] = 0;
  Graph[4][4] = 0;
  Graph[4][5] = 2;
  Graph[4][6] = 0;

  Graph[5][0] = 0;
  Graph[5][1] = 3;
  Graph[5][2] = 0;
  Graph[5][3] = 0;
  Graph[5][4] = 2;
  Graph[5][5] = 0;
  Graph[5][6] = 1;

  Graph[6][0] = 0;
  Graph[6][1] = 0;
  Graph[6][2] = 0;
  Graph[6][3] = 1;
  Graph[6][4] = 0;
  Graph[6][5] = 1;
  Graph[6][6] = 0;

  u = 0;
  Dijkstra(Graph, n, u);

  return 0;
}

Output

Distance from source to 1: 3
Distance from source to 2: 1
Distance from source to 3: 2
Distance from source to 4: 4
Distance from source to 5: 4
Distance from source to 6: 3

 

 

Advantages of Dijkstra’s algorithm

  1. It is its little complexity which is almost linear.

  2. Dijkstra algorithm can be used to calculate the shortest path between a single node to all other nodes and a single source node to a single destination node by stop the algorithm once the shortest distance is achieved for the destination node.

  3. This algorithm only works for directed graph, weighted graphs and all edges should have non-negative values.

 

 

Disadvantage of Dijkstra’s algorithm

 

  1. This algorithm does an obscured exploration that consumes a lot of time while processing,

  2. It is not able to handle negative edges.

  3. As it heads to the acyclic graph, so can’t achieve the accurate shortest path and there is a need to maintain tracking of vertices, have been visited

 

 

Dijkstra’s Algorithm Applications

 

  1. In social networking applications
  2. In a telephone network
  3. To find the locations in the map

 

 

 

Dijkstra’s Algorithm Complexity

Time Complexity

O(E Log V)

Where, E is the number of edges 

            V is the number of vertices.

Space Complexity

O(V)

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *