Untitled
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; }