C program for bellman ford shortest path?

Answer 1

#include

#includeclass spath{int costmatx[10][10]; //cost matrixint n,s; //no of verticesint dist[10]; //to store distancepublic:void read_graph(); //function to read the weighted graphvoid source_vertex(); // from where the distance has to be calculatedvoid shpath(); // to find the shortest pathvoid display(); // to display the total cost for each distance};void spath::read_graph(){int i,j; //loop variablescout<<"Enter the no. of vertices in your graph ";cin>>n; //number of verticescout<<"enter '0' if there is no path\n";for(i=1;i<=n;i++){for(j=1;j<=n;j++){cout<<"enter the cost from " << i <<" to "<< j<<" ";cin>>costmatx[i][j];}}}void spath::source_vertex(){cout<<"enter the source vertix";cin>>s; //source vertex}void spath::shpath(){int mv,i,j;static int f[10];f[s]=1; //changing flag of source vertex to 1;for(i=1;i<=n;i++)dist[i]=costmatx[s][i]; //assigning weight or cost to each vertex s,ifor(int k=1;k<=n;k++){int min=1000; //think y minimum is 1000??for(i=1;i<=n;i++)if((f[i]!=1) && (dist[i]{min=dist[i];mv=i;}f[mv]=1;for(i=1;i<=n;i++)if((f[i]!=1)&&(dist[mv]+costmatx[mv][i]dist[i]=dist[mv]+costmatx[mv][i];}}void spath::display(){for(int i=1;i<=n;i++)cout<<"Ditance from "<}void main(){spath sp;clrscr();sp.read_graph();sp.source_vertex();sp.shpath();sp.display();getch();}

Answer 2

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;

}

Answer 3

#include<stdio.h>

#include<stdlib.h>

#include<unistd.h>

#include<unistd.h>

#include<string.h>

#include<math.h>

#define IN 99

#define N 4

int dijkstra(int cost[][N], int source, int target);

int dijsktra(int cost[][N],int source,int target)

{

int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;

char path[N];

for(i=1;i< N;i++)

{

dist[i] = IN;

prev[i] = -1;

}

start = source;

selected[start]=1;

dist[start] = 0;

while(selected[target] ==0)

{

min = IN;

m = 0;

for(i=1;i< N;i++)

{

d = dist[start] +cost[start][i];

if(d< dist[i]&&selected[i]==0)

{

dist[i] = d;

prev[i] = start;

}

if(min>dist[i] && selected[i]==0)

{

min = dist[i];

m = i;

}

}

start = m;

selected[start] = 1;

}

start = target;

j = 0;

while(start != -1)

{

path[j++] = start+65;

start = prev[start];

}

path[j]='\0';

strrev(path);

printf("%s",path);

printf("%s", path);

return dist[target];

}

main()

{

int cost[N][N],i,j,w,ch,co;

int source, target,x,y;

printf("\tShortest Path Algorithm(DIJKSRTRA's ALGORITHM\n\n");

for(i=1;i< N;i++)

for(j=1;j< N;j++)

cost[i][j] = IN;

for(x=1;x< N;x++)

{

for(y=x+1;y< N;y++)

{

printf("Enter the weight of the path between node %d and %d: ",x,y);

scanf("%d",&w);

cost [x][y] = cost[y][x] = w;

}

printf("\n");

}

printf("\nEnter The Source:");

scanf("%d", &source);

printf("\nEnter The target");

scanf("%d", &target);

co = dijsktra(cost,source,target);

printf("\nShortest Path: %s %d:\n",path,co);

}