20.md

Dijkstra

Method 1

vector <int> dijkstra(int N, vector<vector<int>> adj[], int S)
    {
        
        vector<int>distance(N,INT_MAX);
        distance[S]=0;
        
        queue<pair<int,int>>q;
        q.push({S,0});
        
        while(!q.empty())
        {
            int node=q.front().first;
            int d=q.front().second;
            q.pop();
            
            for(auto it:adj[node])
            {
                int neigh=it[0];
                int neighDist=it[1];
                
                if(d+neighDist<=distance[neigh])
                {
                     distance[neigh]=d+neighDist;
                     q.push({neigh,distance[neigh]});
                }
            }
        }
        
         for(auto &a : distance)
            if(a==INT_MAX)a = -1;
        return distance ;
        
    
    }

Method 2

vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
    {
        priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
       
        vector<int>dis(V, 1e9);
       
        dis[S]=0;
        pq.push({0, S});
       
        while(!pq.empty())
        {
            int nodedis=pq.top().first;
            int node= pq.top().second;
            pq.pop();
           
            for(auto it:adj[node])
            {
                int adjnode=it[0];
                int edgewt= it[1];
               
                if(dis[adjnode]>nodedis+edgewt)
                {
                    dis[adjnode]=nodedis+edgewt;
                     pq.push({dis[adjnode], adjnode});
                }
            }
        }
       
        return dis;
    }

Method 3

vector <int> dijkstra(int V, vector<vector<int>> adj[], int S)
    
    {
        // Create a set ds for storing the nodes as a pair {dist,node}
        // where dist is the distance from source to the node.
        // set stores the nodes in ascending order of the distances 
        set<pair<int,int>> st; 

        // Initialising dist list with a large number to
        // indicate the nodes are unvisited initially.
        // This list contains distance from source to the nodes.
        vector<int> dist(V, 1e9); 
        
        st.insert({0, S}); 

        // Source initialised with dist=0
        dist[S] = 0;
        
        // Now, erase the minimum distance node first from the set
        // and traverse for all its adjacent nodes.
        while(!st.empty()) {
            auto it = *(st.begin()); 
            int node = it.second; 
            int dis = it.first; 
            st.erase(it); 
            
            // Check for all adjacent nodes of the erased
            // element whether the prev dist is larger than current or not.
            for(auto it : adj[node]) {
                int adjNode = it[0]; 
                int edgW = it[1]; 
                
                if(dis + edgW < dist[adjNode]) {
                    // erase if it was visited previously at 
                    // a greater cost.
                    if(dist[adjNode] != 1e9) 
                        st.erase({dist[adjNode], adjNode}); 
                        
                    // If current distance is smaller,
                    // push it into the queue
                    dist[adjNode] = dis + edgW; 
                    st.insert({dist[adjNode], adjNode}); 
                 }
            }
        }
        // Return the list containing shortest distances
        // from source to all the nodes.
        return dist; 
    }