//Syed Rais Ahmad
//CIS 651
//Shortest distance between two nodes.

#include "stdafx.h"
#include <iostream.h>

#define INFINITY 9999
#define MAXNODES 5
#define MEMBER 1
#define NONMEMBER 0

class llNode
{
public:
	int value;
	llNode * nxtNode;
};

//link list defined
class lList
{
private:
	llNode * head;
public:
	lList(); 
	~lList();
	void Insert(int);
	bool Find(int);

};


//create head and put NULL values in it.
lList::lList()
{
	head = new llNode; 
	head->nxtNode=NULL;
	head->value=NULL;
}

//Destroy/free list/memory
lList::~lList()
{
	delete head;
} 


//Insert to the tail of link list
void lList::Insert(int InsertInt)
{
	llNode * ptr=head; 

	while(ptr->nxtNode)  //go all the way to NULL-pointing/last node
		ptr=ptr->nxtNode; 

	ptr->nxtNode=new llNode; 
	ptr=ptr->nxtNode; // temporary pointer holds new value's Insertress
	ptr->value=InsertInt; // Insert a value to new value
	ptr->nxtNode=NULL; //make next value of new value point to NULL
}


bool lList::Find(int n)
{
	llNode * ptr=head; 
	bool result=false;
	while((ptr=ptr->nxtNode) && !result) 
		if (ptr->value==n) result=true;
	return result;
}

class wtMatrix
{
	int wM[MAXNODES][MAXNODES];
	Weight(int,int);
public: 
	ShortPath(int,int);
	wtMatrix();
};


wtMatrix::wtMatrix()
{
	int i=0,j=0;
	for(i=0;i<MAXNODES;i++)
	{
		for(j=0;j<MAXNODES;j++) wM[i][j]=9999;
	}
	wM[0][1]=wM[0][4]=1;
	wM[1][2]=1;wM[1][3]=1;
	wM[2][3]=1;
	wM[4][1]=1;
}

int wtMatrix::Weight(int n1, int n2)
{
	return (wM[n1-1][n2-1]);
}

int wtMatrix::ShortPath(int s,int t)
{
	int distance[MAXNODES];//,perm[MAXNODES];
	int current,i,k,dc;
	int smalldist,newdist;
	lList perm;
//no permanent nodes and all distance are infinity
	for(i=0;i<MAXNODES;i++) 
	{
		distance[i]=INFINITY;
	}
//s, the initial node is put into permanent array and distane to itself
//is set to zero.
	perm.Insert(s);
	distance[s]=0;
	current=s;

	while(current != t)
	{
		smalldist=INFINITY;
		dc=distance[current];
		for(i=0;i<MAXNODES;i++)
			if (!perm.Find(i)) {
				newdist=dc+wM[current][i];
				if (newdist < distance[i]) 
				{
					distance[i]=newdist;
				}
				if(distance[i]<smalldist)
				{
					smalldist=distance[i];
					k=i;
				}
			}
			current=k;
			perm.Insert(current);
	}
	return distance[t];
}
	

main()
{
	wtMatrix  wm;
	cout << wm.ShortPath(0,3);
	return 0;
}