Program for Dijkstra’s Algorithm for Adjacency List Representation in C++

In this tutorial, we will learn a program for Dijkstra’s Algorithm for Adjacency List Representation in C++.

Dijkstra’s Algorithm

Dijkstra’s Algorithm is a greedy search algorithm that is used to set a vertex as source and find the relative shortest distance of all the other vertices in the graph from the source.  The solution that we’re going to be looking at has a time complexity of O(V^2), however, this problem can be solved using a min-heap with a time complexity of O(ElogV), where V is the number of vertices and E is the number of edges.

The code for Dijkstra’s algorithm maintains two arrays- dist and visited. The dist array holds the distances from the respective vertex to the source vertex and the visited array holds boolean values to indicate whether a particular vertex has been visited or not. Let’s take a look at the code and then we’ll go through the explanation.

The code and it’s explanation

using namespace std;
#include <iostream>
#include <climits>

int findmindist(int V,int* dist,bool* visited){
    int mdv=-1;
    for(int j=0;j<V;j++){
        
        if(visited[j]==false&&(mdv==-1||dist[j]<dist[mdv])){
            mdv=j;
        }
    }
    return mdv;
}
int main()
{
  int V, E;
  cin >> V >> E;


  int ** edges=new int*[V];
  for(int i=0;i<V;i++){
    edges[i]=new int[V];
    for(int j=0;j<V;j++){
        edges[i][j]=0;
    }
  }

  bool* visited=new bool[V];
  int* dist=new int[V];
    
  for(int i=0;i<E;i++){
    int ei,ej,wi;
    cin>>ei>>ej>>wi;
    edges[ei][ej]=wi;
    edges[ej][ei]=wi;
  }

  for(int i=0;i<V;i++){
    visited[i]=false;
    dist[i]=INT_MAX;
  }
  dist[0]=0;
  int count=0,i=0;
  while(count!=V-1){
    i=findmindist(V,dist,visited);
    visited[i]=true;
    for(int j=0;j<V;j++){
        if(edges[i][j]!=0&&visited[j]==false){
            if(edges[i][j]+dist[i]<dist[j]){
                dist[j]=dist[i]+edges[i][j];
            }
        }
    }
   
    count++;
  }

  for(int i=0;i<V;i++){
    cout<<"Vertex : "<<i<<"     Distance to Source : "<<dist[i]<<endl;
  }
    
    
  return 0;
}

The findmindist() function returns the index of the element that hasn’t been visited yet and is at the shortest distance from the source vertex. The 0th vertex is set as the source because it is the first unvisited vertex. This function is called at every iteration of the for loop in the main() function that runs for V iterations. After finding the vertex at the shortest distance from the source, it checks whether the distance of the respective index from the source is shorter than the current distance from the source stored in the dist array and then sets the new value of the distance if it is. After the loop ends, the dist array has been updated with the final values and the code is complete.

Let’s take a look at an example with the following graph-

Input

4 5 
0 1 3
0 2 2
0 3 5
1 2 4
2 3 8

Output

Vertex : 0 Distance to Source : 0
Vertex : 1 Distance to Source : 3
Vertex : 2 Distance to Source : 2
Vertex : 3 Distance to Source : 5

Check whether a Matrix is a Latin Square or not in C++