Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
1.4 kB
0
Indexable
Never
 //undirected weighted graph
#include<vector>
#include<unordered_map>
#include<list>
#include<set>

vector<int> dijkstra(vector<vector<int>> &vec, int vertices, int edges, int source) {
    
    //make adjlist
    unordered_map<int, list<pair<int,int>>> adjlist;
    for(int i=0;i<edges;i++){
        int u=vec[i][0];
        int v=vec[i][1];
        int w=vec[i][2];
        adjlist[u].push_back(make_pair(v,w));  //first node, seocnd dist
        adjlist[v].push_back(make_pair(u,w));
    }

    //distance of node from source node vector
    vector<int> dist(vertices,INT_MAX);
    int src=0;
    dist[src]=0;

    //using set as priority queue
    set<pair<int,int>> st;
    st.insert(make_pair(0,src));

    while(!st.empty()){
        auto top =*(st.begin());
        int topnode=top.second;
        int nodedist=top.first;
        st.erase(st.begin());

        for (auto nbr:adjlist[topnode]){

            if(nodedist + nbr.second < dist[nbr.first]){
                auto record =st.find(make_pair(dist[nbr.first],nbr.first));
                if(record!=st.end()){
                    st.erase(record);
                }

            
                dist[nbr.first]=nodedist +nbr.second;

            st.insert(make_pair(dist[nbr.first],nbr.first));
            }
        }
    }
    return dist;

}