Let’s just look at how the algorithm finds out that there’s such a cycle. If there’s a negative-weight cycle, after |V|-1 iterations of relaxing all edges, there are still vertices that could have smaller distance value, and those are the vertices participating in a negative-weight cycle. So, if after |V|-1-th iteration, there’s a vertex v that can be relaxed through edge (u,v), therefore that vertex is on a negative cycle. Acordingly, vertex u is also on the same negative cycle. Thus, we can list a negative cycle by looking at relaxable vertices and walking the path out a vertex, until we reach the initial vertex again.

Traslation of the above description in C++ is as follows:

/**
 * Listing vertices of a negative-weight cycle in a/n un/directed graph
 * using Bellman-Ford algorithm.
 * Copyright (C) 2010 Ali Rabiee  (http://alirabiee.com/).  All  rights
 * reserved.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 *  If you  have modified  this program, you  are required to mark it in
 * reasonable ways as different from the original version.
 *
 *  THERE  IS NO  WARRANTY FOR THE  PROGRAM, TO  THE EXTENT PERMITTED BY
 * APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT
 * HOLDERS  AND/OR  OTHER PARTIES  PROVIDE THE PROGRAM  "AS IS"  WITHOUT
 * WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMA-
 * NCE OF  THE PROGRAM IS WITH YOU. SHOULD  THE PROGRAM PROVE DEFECTIVE,
 * YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
 *
 * IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
 * WILL ANY  COPYRIGHT HOLDER, OR  ANY OTHER PARTY  WHO MODIFIES  AND/OR
 * CONVEYS THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
 * INCLUDING ANY  GENERAL, SPECIAL, INCIDENTAL  OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT
 * NOT  LIMITED  TO LOSS OF  DATA OR DATA  BEING RENDERED  INACCURATE OR
 * LOSSES SUSTAINED BY YOU OR THIRD PARTIES  OR A FAILURE OF THE PROGRAM
 * TO OPERATE  WITH ANY OTHER  PROGRAMS), EVEN  IF SUCH  HOLDER OR OTHER
 * PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
 *
 *  You  should  have received a copy of the  GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  Enjoy the codes ;)
 *
 */
#include <iostream>
#include <map>
#include <vector>
#include <stack>

using namespace std;

struct Edge {
	int u /* from vertex */,
		v /* to vertex   */,
		w /* weight      */;
	Edge(){}
	Edge(int a, int b, int c = 0) { u=a; v=b; w=c; }
};

#define VMAX 100 //maximum number of vertices
#define EMAX VMAX*VMAX //maximum number of edges
#define UVPAIR Edge // a (u,v) pair
#define ELIST vector<Edge> //list of edges

/**
 * Bellman-Ford algorithm
 *
 * @param	int[]	Distance vector
 * @param	ELIST&	Edges using adjacency list structure
 * @param	int		Number of vertices
 * @param	int		Source vertex
 * @return	UVPAIR	u and v vertices on the negative-weight cycle. (-1,-1) if there's no cycle.
 */
UVPAIR bellman_ford(int d[], ELIST &e, int V, int s = 0) {
	UVPAIR r(-1,-1);

	for(int i=0; i<V;i++)
		d[i] = 0xffffff; // initilializing the elements to infinity
	d[s] = 0; // setting source distance to zero

	//relaxing edges |V|-1 times
	for(int i=1; i<V; i++)
		for(ELIST::iterator it=e.begin(); it!=e.end(); it++)
			d[it->v] <?= d[it->u] + it->w;

	//Looking for a negative cycle;
	for(ELIST::iterator it=e.begin(); it!=e.end(); it++)
		if(d[it->v] > d[it->u] + it->w) {
			d[it->v] = d[it->u] + it->w;
			r = *it;
			break;
		}
	return r;
}

/**
 * List the vertices in a negtive-weight cycle, given a participant edge.
 *
 * @param	int[]	Distance vector
 * @param	ELIST[]	Adjacency lists
 * @param	UVPAIR	A participant edge
 */
void list_cycle(int d[], ELIST adjList[], UVPAIR e) {

	cout << e.u;

	Edge t = e;

	do {
		for(ELIST::iterator it=adjList[t.v].begin(); it!=adjList[t.v].end(); it++) {
			if(d[it->v] > d[it->u] + it->w) {
				d[it->v] = d[it->u] + it->w;
				t = *it;
				break;
			}
		}
		cout << " " << t.u;
	} while( t.v != e.u );
	cout << endl;
}

int main() {
	int n, ne, d[VMAX];
	ELIST e;
	ELIST adjList[VMAX];

	int u,v,w;

	cout << "Enter the number of vertices: ";
	cin  >> n;
	cout << "Enter the number of edges: ";
	cin  >> ne;
	cout << "Describe "<< ne <<" edge(s) as (from,to,weight):\n";
	cout << "# Vertex index starts from 0.\n\n";

	for(int i=0; i<ne; i++) {
		cin >> u >> v >> w;
		e.push_back( Edge(u,v,w) );
		adjList[u].push_back( Edge(u,v,w) );
	}

	UVPAIR p =
		bellman_ford(d, e, n);

	if(p.u<0)
		cout << "No negative-weight cycle found.";
	else {
		cout << "Negative-weight cycle: ";
		list_cycle(d, adjList, p);
	}

	return 0;
}

I hope it was useful, and let me know if you have any questions.

—
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Exercise 24.1-6.

I wonder what the purpose of this research is. Is that for finding:

• who runs faster?
• who jumps longer? or
• who has chance since his/her birthday?

I think nothing is predictable about the purpose of the projects being defined here.

A tasty sandwitch is great as long as it isn’t spoiled. Defining several arbitrary topics is a good idea, but constraining each topic to only one team, happended to force many to select a different topic than what they wanted; turning the research into an overhead in their programs, and you know what the output of such research could be.

Indeed, why most iranian cannot stop thinking of ways to bypass the filtering system?