Sorry for any inconvenience I am a beginner at C++ and was stuck with an empty set... Thank you for the helpful comments that helped me figure out what the problem was
I wrote a C++ code for a question in which I need to use Dijkstra's shortest path algorithm in n*log(n) time and so I am using set of pairs to obtain the vertex with shortest distance from source vertex. The code was not giving any errors at runtime but it wasn't giving the output either. So to see where it was getting stuck I used cout statements at certain points in the code and figured that the code is stopping execution right after the erase statement.
The statement is used in the code for erasing the first pair in the set and so the iterator pointing to set.begin() of the set is given as argument. It was earlier written in the format set.erase(iterator), but after searching for this problem on stack overflow I found someone saying iterator=set.erase(iterator) will solve the problem. I tried that and it still was getting stuck at that line, neither stopping execution and returning to the terminal nor giving a runtime error. I don't know what is wrong with this so I thought I would get some help here.
I am providing my code and a screenshot of the running too I would really appreciate your help.
#include<bits/stdc++.h>
using namespace std;
# define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
# define ll long long int
#define mod 1000000007
int n;
set<pair<int, int>> dist;
void dij(vector<pair<int, int>> tree[], int decided[], int d[], vector<int>path[]) {
int mindist=INT_MAX, ind=0;
auto it=dist.begin();
ind=it->second;
cout<<"inbetween"<<endl;
dist.erase(it);
cout<<"inbetween"<<endl;
decided[ind]=1;
for(int i=0; i<tree[ind].size(); i++) {
int update=d[ind]+tree[ind][i].second;
int previous=d[tree[ind][i].first];
if(update<previous) {
pair<int, int>p=make_pair(previous, tree[ind][i].first);
dist.erase(dist.find(p));
p=make_pair(update, tree[ind][i].first);
dist.insert(p);
path[tree[ind][i].first]=path[ind];
cout<<*path[tree[ind][i].first].begin()<<endl;
path[tree[ind][i].first].push_back(tree[ind][i].first);
}
d[tree[ind][i].first]=min(update, previous);
}
}
int main()
{
int edges;
cin>>n>>edges;
vector<pair<int, int>> graph[n];
set<pair<int, int>> dist;
for(int i=0; i<edges; i++) {
int x, y, weight;
cin>>x>>y>>weight;
x--; y--;
graph[x].push_back({y, weight});
graph[y].push_back({x, weight});
}
int src=1;
//cin>>src;
cout<<"here"<<endl;
src--;
int d[n];
for(int i=0; i<n; i++) {
if(src==i) {
dist.insert({0, i});
d[i]=0;
}
else {
dist.insert({INT_MAX, i});
d[i]=INT_MAX;
}
}
int decided[n]={0};
vector<int> path[n];
path[src].push_back(src);
for(int i=0; i<n; i++) dij(graph, decided, d, path);
if(path[n-1].begin()==path[n-1].end()) cout<<-1<<endl;
for(auto it=path[n-1].begin(); it!=path[n-1].end(); it++) cout<<*it+1<<" ";
cout<<endl;
}
Image of the running code: Note that the highlighted lines are the problematic ones neither does iterator manipulation exist in the part of code that is getting stuck nor is the iterator accessed again after erasing.
It is only printing the line before the erase statement and not printing the one after...
The problem as told by user4581301 in the comments was that the iterator was pointing to the end() of the set, which means the set was empty as it was initialized to point to begin() of the set. Thus an undereferencable iterator was dereferenced resulting in undefined behavior, (this means it may not necessarily give a runtime error but rather provide an output when dereferenced). Although the program thus gets stuck at this line as a result of this invalid accessing.
The fault in the code was that set was defined globally but then was refined by the same name inside main, this meant when the values are filled in the set inside main, they are filled in the set that was defined within main not the one defined globally. But when accessing the set in the function dij, the global set is accessed which is actually empty!
Removing the redefinition in main would resolve the issue.
The above code thus works perfectly fine. Below is the screenshot of the working code's output:
Here are some of the links provided in the comments that helped:
P.S. The code finds the path through which the shortest distance between vertex 1 and vertex n of a graph with weighted edges can be obtained, in O(n*log(n)).
Thank you.