Problem Statement

Given a weighted, undirected and connected graph of V vertices and E edges, Find the shortest distance of all the vertex's from the source vertex S.

Note:

The Graph doesn't contain any negative weight cycle.

Problem Link

Implementing Dijkstra Algorithm | Practice | GeeksforGeeks

Reference Link

Dijkstra's Shortest Path Algorithm using priority_queue of STL - GeeksforGeeks

Code (Using BFS and Queue)

// Using Adjacency Matrix
# define pp pair<int,int>
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)
    {
        priority_queue<pp,vector<pp>,greater<pp>> pq;
       
        vector<int> weight(V,INT_MAX);
        pq.push({0,S});
        
        weight[S] = 0;
       
        vector<vector<int> > adj_mat(V, vector<int>(V, INT_MAX)); // weight matrix
        for(int i=0; i<V; i++)
        {
            adj_mat[i][i] = 0;
            
            for(int j=0; j<adj[i].size(); j++)
                adj_mat[i][adj[i][j][0]] = adj[i][j][1];
        }
                
        while(!pq.empty())
        {
            auto p = pq.top();
            int u = p.second;
            int wt = p.first;
            pq.pop();
            for(int i=0;i<adj_mat[u].size();i++)
            {
                if( adj_mat[u][i]!=INT_MAX and 
                weight[i] > wt + adj_mat[u][i] )
                
               {
                   
                    weight[i] = wt + adj_mat[u][i];
                    pq.push({weight[i],i});
               }
            }
           
        }
        return weight;
    }
};

// Using Adjacency list 
typedef pair<int,int> pp;
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)
    {
            vector<pair<int,int>> adj_list[V+1];
            
            for(int i=0;i<V;i++)
            {
                for(auto list:adj[i])
                {
                    adj_list[i].push_back({list[0],list[1]});
                }
            }
            vector<int> weight(V,INT_MAX);
            
            priority_queue<pp,vector<pp>,greater<>> pq;
            
            pq.push({0,S});
            weight[S] = 0;
            
            while(!pq.empty())
            {
                int u = pq.top().second;
                int wt = pq.top().first;
                pq.pop();
                
                for(auto p:adj_list[u])
                {
                    int v = p.first;
                    
                    if(weight[v]>wt+p.second)
                    {
                        weight[v] = wt+p.second;
                        pq.push({weight[v],v});
                    }
                }
            }
            
            
            return weight;
    }
};

Some Important Points