use Bellman ford algo. to find a negative cycle

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

use Bellman ford algo. to find a negative cycle

Post by lonelyone »

How to use Bellman ford algo. to find a negative cycle.
Could someone tell me how to do it.
I mean find the path v1...vk is a negative cycle.
I wanna to find this path.

Thanks a lot.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »


kodylau
New poster
Posts: 1
Joined: Wed Aug 13, 2008 9:12 am

Re: use Bellman ford algo. to find a negative cycle

Post by kodylau »

I have the same question. I know Bellman-Ford algo. can judge if a negative cycle exists.
But I want to know how I can find out one negative cycle.

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Re: use Bellman ford algo. to find a negative cycle

Post by maxdiver »

Execute the usual Ford-Bellman Algorithm (N or N-1 iterations); also save 'parents'.
Then execute one more iteration, and if some changes in dists occur on this extra iteration, than at least one negative cycle exists.
Let firstchanged be any vertex, distance to which had changed. Then just go through its parents, push visited vertices into some array, and mark them 'used'; when we'll try to visit vertex that is already used - stop, and this vertex (not neccesarily firstchanged; let's name it 'lastvisited') is vertex belonging to the negative cycle. So, find in array of visited vertices vertex 'lastvisited', and this part of path will be the answer.
If my description is difficult to understand, here is my code:

Code: Select all

typedef pair<int,int> rib;
typedef vector<rib> graf_line;
typedef graf_line::iterator graf_iter;
typedef vector<graf_line> graf;

const int inf = 1000*1000*1000;


int main()
{
	int n;
	graf g;
	... reading graph ...

	vector<long long> d (n, inf);
	d[0] = 0;
	vector<int> from (n, -1);
	from[0] = 0;
	bool anychanged;
	int firstchanged;
	for (int count=1; count<=n; count++)
	{
		anychanged = false;
		for (int v=0; v<n; v++)
			if (d[v] < inf)
				for (graf_iter i=g[v].begin(); i!=g[v].end(); ++i)
				{
					int to = i->first, l = i->second;
					if (d[to] > d[v]+l)
					{
						d[to] = d[v]+l;
						from[to] = v;
						if (!anychanged)
						{
							anychanged = true;
							firstchanged = to;
						}
					}
				}
	}

	if (!anychanged)
		puts ("NO");
	else
	{
		puts ("YES");

		vector<int> path;
		path.reserve (n+1);
		path.push_back (firstchanged);
		vector<char> used (n);
		used[firstchanged] = true;
		int last = firstchanged;
		for (int cur=from[firstchanged]; !used[cur]; last=cur=from[cur])
		{
			path.push_back (cur);
			used[cur] = true;
		}
		path.push_back (last);
		path.erase (path.begin(), find (path.begin(), path.end(), last));
		reverse (path.begin(), path.end());

		printf ("%d\n", (int)path.size());
		for (size_t i=0; i<path.size(); i++)
			printf ("%d ", path[i]+1);
	}

}

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Re: use Bellman ford algo. to find a negative cycle

Post by maxdiver »

Btw, I've discovered a simpler way to restore the negative cycle after executing the Ford-Bellman.
So, we've got vertex 'firstchanged', and just repeat the following N times: firstchanged = parent[firstchanged].
After that we are surely inside the negative cycle (not in any of its 'tails'), and we can simply iterate firstchanged = parent[firstchanged] and output firstchanged, until firstchanged comes to it first value again.

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Re: use Bellman ford algo. to find a negative cycle

Post by marcadian »

Code: Select all

for(;!used[firstchanged]; firstchanged  = parent[firstchanged])
{
path[++idx] = firstchanged;
used[firstchanged] = true;
}

print from the first occurence of firstchanged in path, until idx


Post Reply

Return to “Algorithms”