路由选择算法源程序（最短路径算法）

路由选择算法，即最短路径算法，并附有程序说明的。

  #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