Bellman-Ford algorithm for Single Source Shortest Path
Last Update: 25 August, 2009

Problem: The Bellman–Ford algorithm, a label-correcting algorithm,[1] computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm solves the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman–Ford is usually used only when there are negative edge weights.

 

My Code:

/*
The input file starts with a line containing the number of cases c to be analyzed.
The input file starts with a line containing the number of node (1<=n<=1000) and the
number of edge (0<=n<=2000) . The node are numbered from 0 through n-1 .
For each edge a line containing three integer numbers x, y and t is given.
These numbers indicate that  x is connected with y, with cost t (-1000<=t<=1000) 

Sample Input:
2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
Sample Output:
possible
not possible

*/

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define INF  1073741822
#define EPS  0.000000001
#define MAX(a,b)  ((a>b)?a:b)
#define MIN(a,b)  ((a<b)?a:b)
#define CLEAR(A,N)  (memset(A,0,(N)*sizeof(A[0])))
#define VI vector<int>
#define VIT vector<int>::iterator



class NodeType
{
public:
	int n,cost;
};

int d[1002];
vector<NodeType> v[1002];

bool BellmanFord(int s, int n)
{
	int i,j,k,flag;
	NodeType t;
	for(i=0;i<n;i++)
		d[i]=INF;
	d[s]=0;
	for(i=1;i<n;i++) // a loop of V-1 time
	{
		flag=0;
		for(j=0;j<n;j++)
		{
			for(k=0; k<v[j].size();k++)
			{
				t=v[j][k];
				if(d[t.n]>d[j]+t.cost)
				{
					d[t.n]=d[j]+t.cost;
					flag=1;
				}
				/*	if(d[j]>d[t.n]+t.cost)  // if the edge's are undirected, use this
				{
					d[j]=d[t.n]+t.cost;
					flag=1;
				}*/
			}
		}
		if(flag==0)
			break;
	}

	for(j=0;j<n;j++)
	{
		for(k=0;k<v[j].size();k++)
		{
			t=v[j][k];
			if(d[t.n]>d[j]+t.cost)
				return false;
		}
	}
	return true;
}

int main()
{
	
	//freopen("in.txt","rt",stdin)
	//freopen("out.txt","wt",stdout)

	int i,n,m,a,b,c,test;

	scanf("%d",&test);
	while(test--)
	{
		scanf("%d %d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			NodeType t;
			t.n=b;
			t.cost=c;
			v[a].push_back(t);
		}
		if(BellmanFord(0,n)==false)
			puts("possible");
		else
			puts("not possible");
		for(i=0;i<n;i++)
			v[i].clear();
	}
	
	
// End of main function.......
return 0;
}


/******  Programmed by:
	~  ORONNO  ~
	www.the1.co.nr
**************************/