use Bellman ford algo. to find a negative cycle

[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]

Google is your best friend: http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

[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]

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]

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]

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