Djikstra's Algorithm.cpp

#include<bits/stdc++.h>
#include "ReadGraph.cpp"
using namespace std;
void DA(vector<vector<int>>A,vector<int>&D,vector<int>&V,priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>&pq,int i)
{
    int a=A.size();
    for(int j=0;j<a;j++)
    {
        if(A[i][j]!=0)
        {
            if(D[i]+A[i][j]<D[j])
            {
                pair<int,int>Node;
                D[j]=D[i]+A[i][j];
                Node.first=D[j];
                Node.second=j;
                pq.push(Node);
            }
        }
    }
    while(!pq.empty())
    {
        int node=pq.top().second;
        if(find(V.begin(),V.end(),node)==V.end())
        {
            V.push_back(node);
            if(V.size()==a)
                return;
            pq.pop();
            DA(A,D,V,pq,node);
        }
        else
            pq.pop();
    }
    return;
}
int main()
{
    auto graph=CreateGraph();
    vector<vector<int>>A=graph.matrix;
    vector<string>N=graph.nodes;
    int c=graph.C,a=N.size();
    cout<<"Enter the source node from which you will calculate the minimum cost path to other nodes:- ";
    string S;
    vector<int>D(a,INT_MAX);
    vector<int>V;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    cin>>S;
    for(int i=0;i<a;i++)
    {
        if(S==N[i])
        {
            D[i]=0;
            V.push_back(i);
            DA(A,D,V,pq,i);
            break;
        }
    }
    cout<<"The minimum costs are:-\n";
    for(int i=0;i<a;i++)
        cout<<D[i]<<" ";
    cout<<"\n";
}