Dijkstra’s shortest path algorithm in C++

In this tutorial, we are going to implement Dijkstra’s shortest path algorithm using sets in C++ language. Before we proceed further let’s take a quick look at what is Dijkstra’s algorithm?

Dijkstra’s algorithm

Dijkstra’s shortest path algorithm is an algorithm which is used for finding the shortest paths between nodes in a graph, for example, road networks, etc. This algorithm is a generalization of the BFS algorithm. The algorithm works by keeping the shortest distance of vertex v from the source in the distance table. After the algorithm finishes, we will have the shortest distance from source s to each other vertex v.

For more information, you can visit,

https://en.wikipedia.org/wiki/Dijkstra’s_algorithm

C++ Code to apply Dijkstra’s shortest path algorithm

We will use two sets in this particular code, one set contains vertices included in shortest path tree and other set includes vertices not yet included in shortest path tree. During every step, we will find a vertex which is in the other set and has a minimum distance from the source.

// A C++ program for Dijkstra's shortest path algorithm.
#include<bits/stdc++.h>
using namespace std;
// Total number of vertices in graph
#define V 9  

// For printing the shortest path
int shortest_path(int dist[], int n)
{
   cout<<"Vertex "<<"\t"<<"Distance from Source\n";
   for (int i = 0; i < V; i++)
   cout<<" \t\t \n"<< i<<" \t\t "<<dist[i];
}

// For calculating minimum distance
int minDist(int dist[], bool Set[])
{
   int min = INT_MAX, min_index;
   for (int i = 0; i < V; i++)
   if (Set[i] == false && dist[i] <= min)
   min = dist[i], min_index = i;
   return min_index;
}

// Calculate shortest paths from source to all other vertices
void Dijkstra(int g[V][V], int src)
{
   int dist[V];
   bool Set[V];
   for (int i = 0; i < V; i++)
   dist[i] = INT_MAX, Set[i] = false;
   dist[src] = 0;
   for (int c = 0; c < V- 1; c++)
   {
      int u = minDist(dist, Set);
      Set[u] = true;
      for (int j = 0; j < V; j++)
    if (!Set[j] && g[u][j] && dist[u] != INT_MAX && dist[u]+ g[u][j] < dist[j])
    {
    dist[j] = dist[u] + g[u][j];
      }
   }
   shortest_path(dist, V);
}

// Driver Program
int main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int G[V][V] = { 
      { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
      { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
      { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
      { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
      { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
      { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
      { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
      { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
      { 0, 0, 2, 0, 0, 0, 6, 7, 0 }};
      Dijkstra(G, 0);  
      return 0;
}

Output:

Vertex  Distance from Source

0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14

Important points:

  • It uses the greedy method ( always choose the nearest closest vertex from the source ).
  • It does not work with negative weights.

You may also learn,




Linked List Reverse Order using C++ STL

How to implement a Queue data structure in Python


Leave a Reply

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