I am facing a small doubt in SPFA problem. My algorithm not working for some test cases
Code:
bool SPFA(int source) //Returns true if there is a negative cycle reachable from source
{
queue<int> q;
for(int i=0;i<=n;i++)
{
cnt[i]=0;
dist[i]=INF;
inqueue[i] = false;
}
dist[source]=0;
q.push(source);
inqueue[source]=true;
while(!q.empty())
{
int v=q.front();
q.pop();
inqueue[v]=false;
for(auto edge:g[v])
{
int to=edge.first;
int w=edge.second;
if(dist[v] + w < dist[to])
{
dist[to] = dist[v] + w;
//dist[to] = max(dist[to], -INF);
if(!inqueue[to])
{
q.push(to);
inqueue[to]=true;
cnt[to]++;
if(cnt[to]>n){
return true;
}
}
}
}
}
return false;
}
Here in my code for a test case : N = 4 src = 1
u v w
1 2 30
2 3 40
3 4 -36
4 3 34
Negative cycle has to be 3->4->3
But my code is not getting any cycles.
Any help would be encouraging