sir in dijkstra’s algorithm I’m getting an error in stl graph.h
what can i do to get rid of that.
and the code is as follows:
#include<bits/stdc++.h>
using namespace std;
template
class Graph{
map<T,list<pair<T,int>>> AdjList;
public:
void AddEdge(T u,T v,int dist,bool bidir=true)
{
AdjList[u].push_back(make_pair(v,dist));
if(bidir)
{
AdjList[v].push_back(make_pair(u,dist));
}
}
void sssp(T source)
{
map<T,int>dist;
//set all the distances to be infinity
for(auto j:AdjList)
{
dist[j.first]=INT32_MAX;
}
//make a set to find out node with a minimum distance
set<pair<int ,T>>s;
dist[source]=0;
s.insert(make_pair(0,source));
while(!s.empty())
{
//find the pair at the front
auto p=*(s.begin());
//b'coz s.begin() is a pointer and *(s.begin()) will give us pair
T node=p.second;
//b'coz second parameter here denotes the node and first parameter denotes the distance
int nodeDistance=p.first;
//it gives the node distance
s.erase(*(s.begin()));
//by this we erase the pair of node and distance will be erased.
//iterate over the neighbours of the current node.
for(auto neighbour:AdjList[node])
{
if(nodeDistance+neighbour.second < dist[neighbour.first])
{
//in the set/priority queue updation is not possible.
// we have to remove the old pair and insert the new pair.
auto f=s.find(make_pair(dist[neighbour.first],neighbour.first));
if(f!=s.end())
{
//here f is an iterator
//if f is not pointing to the end then it means that node has been found,so we will erase that node.
s.erase(f);
}
//insert the new pair
dist[neighbour.first]=nodeDistance+neighbour.second;
s.insert(dist[neighbour.first],neighbour.first);
}
}
}
//lets print distances to all other node
for(auto j:dist)
{
cout<<j.first<<"and its dist is: "<<j.second<<endl;
}
}
};
int main()
{
Graph<int>g;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int key,value,dist;
cin>>key>>value>>dist;
g.AddEdge(key,value,dist,false);
}
g.sssp(0);
return 0;
}