#include”iostream.h”
#include”conio.h”
#include”stdlib.h”
#include”math.h”
#include”graphics.h”

#define MAX 20 //Maximum number of nodes

int h=315,v=238,i,j,x,y,z,s,d,t,n,spath=10000;
struct linkdata
{
int presence; //Indicates presence or absence of link
int length; //Indicates length of link in kms, if present
};
struct coords
{
int m; //X coordinate
int n; //Y coordinate
};
linkdata subnet[MAX][MAX]; //Array holding subnet map
int node[MAX],nodef[MAX]; //Arrays holding list of intermediate nodes
int number[MAX]; //Array holding pointers to contents of int. node arrays
coords points[MAX]; //Array holding X,Y coordinates of graph circles
char names[5]; //Array holding numbers for display in ‘char’ format

void main()
{
//Initialization section
//———–

//Initialize graphics
int gdriver=9,gmode=2;
initgraph(&gdriver,&gmode,”\\tc\\bgi”);
cleardevice();

//Welcome message
cout<<“\n\nShortest Path )”;

//Reset subnet array
for(i=0;i<15;i++)
for(j=0;j<15;j++)
{
subnet[i][j].presence=0;
subnet[i][j].length=10000;
}

//Data entry section
//————-

//Ask user to enter the subnet details
cout<<“\n\nPlease enter the details …”;

//Enter total number of nodes in subnet; maximum 20
cout<<“\n\nEnter the total number of nodes : “;
cin>>t;

//Form array map of subnet
for(i=0;i<t-1;i++)
{
cout<<“\nEnter the number of nodes to which node “<<i+1<<” is connected: “;
cin>>x;
cout<<“\nEnter the numbers of those nodes one by one:”;
for(j=0;j<x;j++)
{
cout<<“\n”<<j+1<<“: “;
cin>>y;
subnet[i][y-1].presence=subnet[y-1][i].presence=1;
cout<<“\nEnter length of link from “<<i+1<<” to “<<y<<” : “;
cin>>z;
subnet[i][y-1].length=subnet[y-1][i].length=z;
}
}

//Enter source & destination node
cout<<“\nEnter the source node number: “;
cin>>s;
cout<<“\nEnter the destination node number: “;
cin>>d;

//Transfer list of nodes (all except source & destination) to a new array
j=0;
for(i=1;i<=t;i++)
if((i!=s)&&(i!=d))
{
node[j]=i-1;
j++;
};

//Shortest path calculation process begins
//—————–
cout<<“\nProcessing…”;
n=0;
z=0;

//Check if a direct link is available; if yes, display directly
if(subnet[s-1][d-1].presence==1)
{spath=subnet[s-1][d-1].length;
goto end;
}

//Else try to find a valid route with intermediate nodes
do
{
n++;

//Reset intermediate node number pointer array
for(i=0;i<n;i++)
number[i]=0;

do
{
//Check if intermediate nodes are being repeated in ‘number[]’ array
x=0;
if (n>1)
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(number[i]==number[j])
{
x=1;
goto ok;
}
ok:

if((subnet[s-1][node[number[0]]].presence==1)&&(subnet[node[number[n-1]]][d-1].presence==1)&&(x==0))
{
x=0;
y=0;
y=subnet[s-1][node[number[0]]].length+subnet[node[number[n-1]]][d-1].length;
if((n-1)>0)
{
j=0;
do
{
if(subnet[node[number[j]]][node[number[j+1]]].presence==0) x=1;
else y=y+subnet[node[number[j]]][node[number[j+1]]].length;
j++;
}
while((j<n-1)&&(x==0));
}
if((x==0)&&(y<spath))
{
spath=y;
for(i=0;i<n;i++) nodef[i]=node[number[i]];
}
}
x=1;
y=0;
z=0;

//Check if all options with current ‘n’ are exhausted
for(i=0;i<n;i++)
if(number[i]<t-3) z=1;

do
{
if((number[n-x])<(t-3))
{
number[n-x]++;
y=1;
}
else
{
number[n-x]=0;
x++;
}
}
while((x<=n)&&(y==0));
}
while(z==1);
}
while((n<t-2)&&(spath==10000));