﻿ Tips And Tutorial - Presented by Oneous!

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
**************************/``````