/*************************************************************************

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