Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Little help in SPFA algorithm for negative cycle in dir graph

Правка en7, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский humblefOOOol 2021-04-16 00:56:57 269
en6 Английский 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 Английский humblefOOOol 2021-04-16 00:43:56 0 (published)
en4 Английский humblefOOOol 2021-04-16 00:43:23 84 (saved to drafts)
en3 Английский humblefOOOol 2021-04-16 00:35:54 0 (published)
en2 Английский humblefOOOol 2021-04-16 00:34:59 22 (saved to drafts)
en1 Английский humblefOOOol 2021-04-16 00:33:09 1260 Initial revision (published)