/*************************************************************************
-> This C++ program is to implement Bellmen Ford algorithm.
-> Bellmen Ford algorithm solves the single source shortest paths
problem in the general case in which edge weights may be negative.
-> This algorithm returns true if the graph contains no
negative-weight cycles that are reachable from the source
else returns the shortest paths from the source.
-> This program works in Microsoft VC++ environment in windows xp
-> Data structures used:
Graph :: Adjacency matrix
-> Header files used :
1)iostream.h
2)stdlib.h
/*************************************************************************/
#include<iostream.h>
#include<stdlib.h>
#define MAX 20
#define INFINITY 9999
class bell_ford
{
private:
int n;
int graph[MAX][MAX];
int start;
int distance[MAX];
int predecessor[MAX];
public:
void read_graph();
void initialize();
void update();
void check();
void algorithm();
};
void bell_ford::read_graph()
{
cout<<“Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<“Enter the adjacency matrix for the graph ::\n”;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>graph[i][j];
cout<<“Enter the start vertex ::”;
cin>>start;
}
void bell_ford::initialize()
{
for(int i=1;i<=n;i++)
{
distance[i]=INFINITY;
predecessor[i]=0;
}
distance[start]=0;
}
void bell_ford::update()
{
for(int i=1;i<=n-1;i++)
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(graph[u][v]!=0)
{
if(distance[v]>distance[u]+graph[u][v])
{
distance[v]=distance[u]+graph[u][v];
predecessor[v]=u;
}
}
}
}
}
}
void bell_ford::check()
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(graph[u][v]!=0)
{
if(distance[v]>distance[u]+graph[u][v])
{
cout<<“does not exist’s “;
return;
}
}
}
}
cout<<“\n\nThere is no negative weight cycle and\n”;
cout<<“****** The final paths and the distacnes are ******\n\n”;
for(int i=1;i<=n;i++)
{
cout<<“path for node “<<i<<” is ::\n”;
int arr[MAX],k=1;
int j=i;
while(predecessor[j]!=0)
{
arr[k]=predecessor[j];
k++;
j=predecessor[j];
}
for(–k;k>0;k–)
cout<<arr[k]<<“->”;
cout<<i<<endl;
cout<<“distance is “<<distance[i]<<endl<<endl<<endl;
}
}
void bell_ford::algorithm()
{
read_graph();
initialize();
update();
check();
}
void main()
{
bell_ford obj;
obj.algorithm();
}
thank you for creating such an easy way to get the soulution of your problem.
incomplete code
this code is wrong .dont waste your time.admin try to cheat you
Hi, I could not understand the following part of your program, I would be very help ful for me if you make me understand the following part
for(k;k>0;k) //is this aiteration OK? why did you do this
cout<<arr[k]<;
I ahve provided my email address pls, mail me.
HAI…..
I tried your algorithm its working fine for positive values and 5 nodes…..
once the no of nodes grows its not working……
i tried with 20 nodes………..
its not working……..
Si que funciona gñan
changed
for(-k; k>0; k-) –>> for(k=k-1; k>0; k–)
works well, and I am very very thankful for your code! Been pleasure to use it.
Best regards.
hi
ive replaced this,
for(-k; k>0; k-) –>> for(k=k-1; k>0; k–)
this gives me this error
error C2059: syntax error : ‘)’
please reply. thankyou
Hey chnge it to for(k=k-1;k>0;k–); try and tell me if you face problem again
in html > is shown as >
hi i did again. i copy and pasted your for statement as it is! and got this error
—————————————————————————–
1>—— Build started: Project: beln, Configuration: Debug Win32 ——
1>Compiling…
1>Bln.cpp
1>.\Beln.cpp(111) : error C2065: ‘k–’ : undeclared identifier
—————————————————————————
please help
hi i did again. i copy and pasted your for statement as it is! and got this error
—————————————————————————–
1>—— Build started: Project: Beln, Configuration: Debug Win32 ——
1>Compiling…
1>Beln.cpp
1>.\Beln.cpp(111) : error C2065: ‘k–’ : undeclared identifier
—————————————————————————
please help
for(k=k-1; k>0; k–)
is this k–
or simply k-
?
U seems to be absolute beginner. it is k– that means k=k-1; Any way i will send you the code that will work in a separate text file tmrw.
hi,
can anybody help me please. i want to display updated cost matrices after each update process using this code. rest is fine. code working fine but i need to display updated cost matrices.
thanks
cout<<"\n\n No negative weights are found \n";
cout<<"****** These are the final Distances ******\n\n";
for(int i=1;i<=Node;i++)
{
cout<<"path for node"<<i<0; k–);
cout<<arr[k]<“;
cout<<i<<endl;
cout<<"Distance is "<<Dist[i]<<endl<<endl<—— Build started: Project: Beln, Configuration: Debug Win32 ——
1>Compiling…
1>Beln.cpp
1>.\Beln.cpp(111) : error C2065: ‘k–’ : undeclared identifier
1>Build log was saved at “file://c:\Users\riki\Documents\Downloads\Beln\Beln\Beln\Debug\BuildLog.htm”
1>Beln – 1 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
could you please send me today on curl.lyke.smoke@gmaildotcom
moreover, i want to display adjacency matrix and update matrices. is it possible to display it? would greatly appreciate!
Thanks for the help in advance,
kind regards
rakesh
idiot make correct code.u cheat us
nice prog
is there a way to get the code to print out the nodes in the path.. and not just the path distance?
#include
#include
#define MAX 20
#define INFINITY 9999
class bell_ford
{
private:
int n;
int graph[MAX][MAX];
int start;
int distance[MAX];
int predecessor[MAX];
public:
void read_graph();
void initialize();
void update();
void check();
void algorithm();
};
void bell_ford::read_graph()
{
cout<>n;
cout<<”Enter the adjacency matrix for the graph ::\n”;
for(int i=1;i<=n;i++)
for(int j=1;j>graph[i][j];
cout<>start;
}
void bell_ford::initialize()
{
for(int i=1;i<=n;i++)
{
distance[i]=INFINITY;
predecessor[i]=0;
}
distance[start]=0;
}
void bell_ford::update()
{
for(int i=1;i<=n-1;i++)
{
for(int u=1;u<=n;u++)
{
for(int v=1;vdistance[u]+graph[u][v])
{
distance[v]=distance[u]+graph[u][v];
predecessor[v]=u;
}
}
}
}
}
}
void bell_ford::check()
{
for(int u=1;u<=n;u++)
{
for(int v=1;vdistance[u]+graph[u][v])
{
cout<<”does not exist’s “;
return;
}
}
}
}
cout<<”\n\nThere is no negative weight cycle and\n”;
cout<<”****** The final paths and the distacnes are ******\n\n”;
for(int i=1;i<=n;i++)
{
cout<<”path for node “<<i<0;k–)
cout<<arr[k]<”;
cout<<i<<endl;
cout<<”distance is “<<distance[i]<<endl<<endl<<endl;
}
}
void bell_ford::algorithm()
{
read_graph();
initialize();
update();
check();
}
void main()
{
bell_ford obj;
obj.algorithm();
}
its giving lots of errors. could u pls help on this part
for(–k;k>0;k–)
Thanks .. a lot…its working for possible number of input
Hi,
What if we’d like to change this code to use the negative negative-weight cycles as well ?
Let’s say we have a 3-dimensional matrix as:
-1 2 4
12 -1 -1
5 8 -1
Thanks…
hi its giving me error
“fatal error C1083: Cannot open include file: ‘iostream.h’: No such file or directory”
i am using vc++ 2008 express edition.
above program is incomplete and need so many changes. can’t execute directly.
313111
Ya, By cheating you i get lot of money and fun:)
one day u will cheat
mother fucker this code completely wrong
bhains ki aankh
manik aap bhand hain ,ja k pogo dekho
abey tere expert cmmnt kisne mange ja jake apni aag bujha
pranay and manik maa chuda loo
Are you this code implements the Bellman-Ford algorithm??..looks very much like Dijsktra’s algorithm to me..cheers