Implementing Dijkstra Algorithm | Practice | GeeksforGeeks

class Solution
{
	public:
	//Function to find the shortest distance of all the vertices
    //from the source vertex S.
    vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
    {
        // Code here
        //Dijkstra's algo
        //adj list, Create a dis array, intitialize with int_max, dis[src]=0,create a priority
        //queue or set where we'll store the dis and node, this priority queue/set would be sorted 
        // by the dis value and anlways the node with the smallest dis value will be at bottom,
        //we'll take out each one by one and then iterate to their adj nodes
        // and check if dis[curr]+wt<dis[child], if true then update the distance array
        vector<int> dis(V,INT_MAX);
        dis[S]=0;
        set<pair<int,int>> pq;
        pq.insert({0,S});
        while(!pq.empty()){
            auto it =*(pq.begin());
            int wt = it.first;
            int node = it.second;
            pq.erase(it);
            for(auto it:adj[node]){
                int ch = it[0];
                int edge =it[1];
                if(wt+edge<dis[ch]){
                    dis[ch]=wt+edge;
                    pq.insert({dis[ch],ch});
                }
            }
        }
        return dis;
        
        
    }
};