Bellman Ford Algo

Reply

Join Date: Jul 2004
Posts: 25
Reputation: Naveen is an unknown quantity at this point 
Solved Threads: 0
Naveen's Avatar
Naveen Naveen is offline Offline
Light Poster

Bellman Ford Algo

 
0
  #1
Aug 2nd, 2004
i have created 3 matrices: 1) Connection Mtrx 2) Metric Mtrx 3) Ans Mtrx.

here from connection mtrx, seeing starting node,i update the ans mtrx which will hold the sequence of node traversal. how do i code to achieve this?

the code problem is coming in function bf().

#include<iostream.h>
#include<conio.h>

class bellford
{
int size,**node,**metric,**ans,count,*temp;
int i,j,k,start_node,pass;

public:
bellford()
{
pass=count=i=j=0;
}

void accept(); // Accepts Number Of Nodes
void create(); // Creates Connection and Metric Matrices
void start(); // Accepts starting node for comm.
void bf(); // Generates Path for Routing
//void make_ans(int,int); // Holds Answers
void oracle(); // Displays Final Answer
};

void bellford::accept()
{
cout<<"Enter size of Matrix:";
cin>>size;
create();
}

void bellford::create()
{
node=new int*[size];
for(i=0;i<size;i++)
node[i]=new int[size];

metric=new int*[size];
for(i=0;i<size;i++)
metric[i]=new int[size];

/*ans=new int*[size];
for(i=0;i<size;i++)
ans[i]=new int[size];

for(i=0;i<size;i++)
{
//ans[i][0]=i+1;
for(j=0;j<size;j++)
{
ans[i][j]=0;
}
}
*/
clrscr();
cout<<"Enter Connection Between Nodes"<<endl<<endl;
cout<<"0:Connection Absent\n1: Connection Present"<<endl<<endl;

for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
if(i==j)
{
node[i][j]=0;
}
else
{
cout<<"Node "<< i+1 <<" -> Node "<<j+1<<": ";
cin>>node[i][j];
cout<<endl;
if(node[i][j]==1)
{
cout<<endl<<"Enter Metric for Node "<< i+1 <<" -> Node "<<j+1<<": ";
cin>>metric[i][j];
cout<<endl;
}
}
}
}
start();
}

void bellford::start()
{
cout<<endl<<"Enter The Starting Node: ";
cin>>start_node;
//cout<<endl;
j=0;
//pass=0;
temp=new int[size];
for(i=0;i<size;i++) // No. of nodes start_node is conn. to
{
if(node[start_node-1][i]==1)
{
temp[j++]=i+1;
cout<<"Temp:"<<j-1<<" : "<<temp[j-1]<<endl;
count++;
}
}
ans=new int*[count]; // No. of rows present in the ans matrix
// Eg.
// 0________
// 1________
// 2________
for(j=0;j<size;j++) // Puttin size of each row as size of full matrix
{ // Eg.
ans[j]=new int[size];// 5-> _ _ _ _ _
} // 5-> _ _ _ _ _
// 5-> _ _ _ _ _
i=0;//Making i=0 to put values of start_node in every row
j=0;
while(i<count)
{
ans[i][0]=start_node;// Eg. 1 _ _ _ _ _
ans[i++][1]=temp[j++];
}

/*for(i=0;i<count;i++) // For temporary chking of values in ans
{
for(j=0;j<size;j++)
{
cout<<i+1<<":"<<j+1<<":"<<ans[i][j]<<endl;
}
cout<<endl;
}*/

pass=1; // We r at pos 0 1 _ _ _ in ans matrix
bf();
}

void bellford::bf()
{
i=0; // Making i=0 to put values of start_node in every row
j=0;
while(i<count)
{
for(j=0;j<size;j++)
{
if(node[ans[i][pass]-1][j]==1)
ans[i][pass+1]=node[ans[i][pass]-1][j]+1;
}
i++;
pass++;
}
}

/*void bellford::make_ans(int x,int y)
{

ans[x][y]=y;
//pass++;
}*/

void bellford::oracle()
{
for(i=0;i<count;i++)
{
for(j=0;j<size;j++)
{
cout<<i+1<<":"<<j+1<<":"<<ans[i][j]<<endl;
}
cout<<endl;
}
}

int main()
{
bellford b;
clrscr();
b.accept();
getch();
b.oracle();
getch();
return 1;
}
Reply With Quote Quick reply to this message  
Join Date: Jun 2004
Posts: 609
Reputation: freesoft_2000 is an unknown quantity at this point 
Solved Threads: 7
freesoft_2000 freesoft_2000 is offline Offline
Practically a Master Poster

Re: Bellman Ford Algo

 
0
  #2
Aug 2nd, 2004
hi everyone,
Try getting the user to input the matrix horizontally and use kramer's rule to break down the matrix.

Yours Sincerely

Richard West
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC