# define SIZE 8
# define INFINITY 99
#include<iostream>
#include<stdlib.h>
using namespace std;
void build(int n);
void minimum(char key);
void table();
void print();
int n,c,mini,y,m;
int mat[SIZE][SIZE];
char name[SIZE];
struct adjac
{
char node,k,hv;
int dv,frend[7];
}ob[SIZE];
int main()
{
cout<<"\nEnter the number of nodes:";
cin>>n;
build(n);
table();
system("cls");
print();
}
void build(int n)
{
int i,j;
for(i=0;i<n;i++)
{
cout<<"\nEnter the name of node "<<i+1<<" : ";
cin>>name[i];
ob[i].node=name[i];
ob[i].dv=0;
ob[i].hv='-';
ob[i].k='F';
}
for(i=0;i<n;i++)
{
c=0;
for(j=0;j<n;j++)
{
cout<<"\nEnter weight from node "<<name[i]<<" to node "<<name[j]<<" : ";
cin>>mat[i][j];
if(mat[i][j]!=0 && mat[i][j]!=INFINITY)
{
ob[i].frend[c++]=j;
}
}
ob[i].frend[c]=-1;
mat[i][i]=0;
}
}
void table()
{
int i,c,j;
char key;
cout<<"\nEnter the name of the key node:";
cin>>key;
minimum(key);
for(j=0;j<n-1;j++)
{
minimum(ob[mini].node);
}
}
void minimum(char key)
{
int i;
for(i=0;i<n;i++)
{
if(ob[i].k=='F')
{
if(ob[i].node==key)
{
ob[i].k='T';
c=0;
while(ob[i].frend[c]!=-1)
{
if(ob[ob[i].frend[c]].k=='F')
{
ob[ob[i].frend[c]].hv=ob[i].node;
if(m++==c)
ob[ob[i].frend[c]].dv+=mat[i][ob[i].frend[c]];
else
if(ob[ob[i].frend[c]].dv>ob[i].dv+mat[i][ob[i].frend[c]] || ob[ob[i].frend[c]].dv==0)
ob[ob[i].frend[c]].dv=ob[i].dv+mat[i][ob[i].frend[c]];
}
c++;
}
break;
}
}
}
y=0;
for(i=0;i<n;i++)
{
if(ob[i].dv!=0 && ob[i].k=='F')
{
if(y++==0)
mini=i;
if(ob[i].dv<ob[mini].dv)
mini=i;
}
}
}
void print()
{
int i;
cout<<"\nNode K dv hv\n\n";
for(i=0;i<n;i++)
{
cout<<ob[i].node<<" "<<ob[i].k<<" "<<ob[i].dv<<" "<<ob[i].hv<<endl<<endl;
}
}
# define INFINITY 99
#include<iostream>
#include<stdlib.h>
using namespace std;
void build(int n);
void minimum(char key);
void table();
void print();
int n,c,mini,y,m;
int mat[SIZE][SIZE];
char name[SIZE];
struct adjac
{
char node,k,hv;
int dv,frend[7];
}ob[SIZE];
int main()
{
cout<<"\nEnter the number of nodes:";
cin>>n;
build(n);
table();
system("cls");
print();
}
void build(int n)
{
int i,j;
for(i=0;i<n;i++)
{
cout<<"\nEnter the name of node "<<i+1<<" : ";
cin>>name[i];
ob[i].node=name[i];
ob[i].dv=0;
ob[i].hv='-';
ob[i].k='F';
}
for(i=0;i<n;i++)
{
c=0;
for(j=0;j<n;j++)
{
cout<<"\nEnter weight from node "<<name[i]<<" to node "<<name[j]<<" : ";
cin>>mat[i][j];
if(mat[i][j]!=0 && mat[i][j]!=INFINITY)
{
ob[i].frend[c++]=j;
}
}
ob[i].frend[c]=-1;
mat[i][i]=0;
}
}
void table()
{
int i,c,j;
char key;
cout<<"\nEnter the name of the key node:";
cin>>key;
minimum(key);
for(j=0;j<n-1;j++)
{
minimum(ob[mini].node);
}
}
void minimum(char key)
{
int i;
for(i=0;i<n;i++)
{
if(ob[i].k=='F')
{
if(ob[i].node==key)
{
ob[i].k='T';
c=0;
while(ob[i].frend[c]!=-1)
{
if(ob[ob[i].frend[c]].k=='F')
{
ob[ob[i].frend[c]].hv=ob[i].node;
if(m++==c)
ob[ob[i].frend[c]].dv+=mat[i][ob[i].frend[c]];
else
if(ob[ob[i].frend[c]].dv>ob[i].dv+mat[i][ob[i].frend[c]] || ob[ob[i].frend[c]].dv==0)
ob[ob[i].frend[c]].dv=ob[i].dv+mat[i][ob[i].frend[c]];
}
c++;
}
break;
}
}
}
y=0;
for(i=0;i<n;i++)
{
if(ob[i].dv!=0 && ob[i].k=='F')
{
if(y++==0)
mini=i;
if(ob[i].dv<ob[mini].dv)
mini=i;
}
}
}
void print()
{
int i;
cout<<"\nNode K dv hv\n\n";
for(i=0;i<n;i++)
{
cout<<ob[i].node<<" "<<ob[i].k<<" "<<ob[i].dv<<" "<<ob[i].hv<<endl<<endl;
}
}
No comments:
Post a Comment