Bellman Ford Algo
 

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

Re: Bellman Ford Algo
 

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