??#include
#include
#include

#define?N?10	//the?num?of?routers
#define?MAX?999?//the?initial?max?delay


typedef?struct?node*?router;?//the?ADT?of?router
typedef?struct?list*?link;?//the?ADT?of?neighborhood?of?each?router
typedef?struct?table*?vector;?//the?ADT?of?the?distance?list?inside?routers

struct?list{
	int?label;
	int?delay;
	link?next;
};

struct?table?{
	int?time;
	int?nextrouter;
};

struct?node?{
	link?neigh;
	vector?tdelay;
};

void?init（router?all?FILE*?fp）??//initiate?the?topologic
{
	link?t;
	int?ij;
	int?neighnumtmplabeltmpdelay;

	for（i=0;i	{
		fscanf（fp“%d\n“&neighnum）;

		all[i].neigh=（link）malloc（sizeof（struct?list））;	//read?the?num?of?neighbour?routers?of?router?i
		//all[i].tdelay=（vector）malloc（N*sizeof（struct?table））;

		t=all[i].neigh;t->next=NULL;

			for（j=0;j		{
			all[i].tdelay[j].time=MAX;	
			all[i].tdelay[j].nextrouter=i;	
		}
		all[i].tdelay[i].time=0;

		for（j=neighnum;j>0;j--）	
		{
			
			t->next=（link）malloc（sizeof（list））;
			t=t->next;	
		fscanf（fp“%d“&tmplabel）;	//read?the?label?of?each?neighbour
		fscanf（fp“%d\n“&tmpdelay）;	//read?the?delay?of?the?link

			t->label=tmplabel;
			t->delay=tmpdelay;
			t->next=NULL;

			all[i].tdelay[tmplabel].time=tmpdelay;
			all[i].tdelay[tmplabel].nextrouter=tmplabel;
		}
		
	}
	//return?all;
}


void?passvector（router?onerouter?all）	//change?the?vector?list?of?one?router
{
	router?tmprouter;

	for（link?tmp=one->neigh->next;tmp;tmp=tmp->next）	//receive?the?lists?passed?from?neigbours?one?by?one
	{
		tmprouter=&all[tmp->label];
		for（int?i=0;i		??if（one->tdelay[i].time>（tmprouter->tdelay[i].time+tmp->delay））	//if?the?path?though?this?neighbour?is?optimal?until?now?update?the?list
		??{
			??one->tdelay[i].time=（tmprouter->tdelay[i].time+tmp->delay）;
			??one->tdelay[i].nextrouter=tmp->label;
		??}
	}

}

void?printtable（router?oneFILE*?outint?t）	//print?the?list?of?one?router?to?output.txt
{	
	for（int?i=0;i		??fprintf（out“%d->%d:?nextrouter?is?%d?time?left?to?reach?dest?is?%d\n?“tione->tdelay[i].nextrouterone->tdelay[i].time）;
	fprintf（out“\n“）;
}

void?main（）
{
	int?ttimes;
	node?allrouter[N];	//varibles?to?store?all?the?data
	table?vector[N][N];
	FILE*?fp;
	FILE*?out;

	fp=fopen（“input.txt““r“）;
	out=fopen（“output.txt““w“）;

	for（t=0;t		allrouter[t].tdelay=vector[t];

	init（allrouterfp）;	//initiate
	for（times=1;times	{
		for（t=0;t			passvector（&allrouter[t]allrouter）;
	}
	for（t=0;t	printtable（&allrouter[t]outt）;

}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????136192??2008-04-14?23:22??ch4-23fengyu\ch4-23fengyu.doc

?????文件???????2917??2008-04-15?18:31??ch4-23fengyu\fengyu.cpp

?????目錄??????????0??2008-04-15?18:40??ch4-23fengyu

-----------?---------??----------?-----??----

???????????????139109????????????????????3