Little help in SPFA algorithm for negative cycle in dir graph

Revision en7, by humblefOOOol, 2021-04-16 00:56:57

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
            
                               19 20 -36
                               20 19 34
                                 

Negative cycle has to be 19->20->19

As queue starts from src(1)

---> No edge from src so it can't visit adjacent vertices so we can't relax edges connected to node.

Can we add an imaginary edge in the graph so that we can traverse ?

Any help would be encouraging.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English humblefOOOol 2021-04-16 00:56:57 269
en6 English humblefOOOol 2021-04-16 00:46:00 9 Tiny change: 'has to be 19->20->19\n\nBut my' -> 'has to be 3->4->3\n\nBut my'
en5 English humblefOOOol 2021-04-16 00:43:56 0 (published)
en4 English humblefOOOol 2021-04-16 00:43:23 84 (saved to drafts)
en3 English humblefOOOol 2021-04-16 00:35:54 0 (published)
en2 English humblefOOOol 2021-04-16 00:34:59 22 (saved to drafts)
en1 English humblefOOOol 2021-04-16 00:33:09 1260 Initial revision (published)