When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

humblefOOOol's blog

By humblefOOOol, history, 3 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it