www.pudn.com > Dijkstra_router.rar > router.cpp

#include "stdio.h" 
#include "conio.h" 
 
#define MAXVEX 20	//最大顶点数 
int n,e;			//全局变量，分别表示顶点数和边数 
 
//----------图的定义,使用邻接矩阵表示------------------- 
 
struct vertex		//顶点的结构 
{ 
	char name;		//顶点名称 
	bool choose;	//----------用于求路径--顶点是否已被圈定 
	char pre;		//顶点标号--用于求路径--表示前驱顶点 
	int num;		//顶点标号--用于求路径--表示起点传递到此总权值 
}; 
struct _graph		//定义一个图 
{ 
	struct vertex vexs[MAXVEX];	//顶点集合 
	int edges[MAXVEX][MAXVEX];	//边集合 
}; 
typedef struct _graph graph; 
 
//------------------------------------------------------ 
 
graph CreatGraph()		//构建一个无向带权图,采用邻接矩阵表示 
{ 
	int i,j,k,w; 
	char b,t; 
	graph adj; 
 
	printf("请注意,此处为无向带权图!\n\n"); 
	printf("请输入顶点数(n)和边数(e):"); 
	scanf("%d,%d",&n,&e); 
 
	for (i = 0; i < n; i++) 
	{ 
		printf("第%d个顶点的名称:",i+1);	 
		adj.vexs[i].name = getche();	//初始化顶点名称 
		adj.vexs[i].num = 32767;		//初始权值为无穷,用32767代替 
		adj.vexs[i].choose = false;		//初始化为未被圈定 
		adj.vexs[i].pre = NULL;			//前驱顶点置空 
 
		for (j = 0; j < n; j++)			//初始化各边权值 
			adj.edges[i][j] = -1;		//-1表示无直达路径 
 
		printf("\n"); 
	} 
	 
	for (k = 1; k <= e; k++)			//获取各边权值 
	{ 
		printf("\n"); 
 L1:	printf("第%d条边=>\n起点:",k); 
		b = getche(); 
		printf("\t终点:"); 
		t = getche(); 
		printf("\t权值:"); 
		scanf("%d",&w); 
 
		i=0; 
		while(i < n && adj.vexs[i].name != b) 
			i++; 
		if (i >= n) 
		{ 
			printf("输入的起点不存在,请重新输入!\n"); 
			goto L1; 
		} 
		j=0; 
		while(j < n && adj.vexs[j].name != t) 
			j++; 
		if (j >= n) 
		{ 
			printf("输入的终点不存在,请重新输入!\n"); 
			goto L1; 
		} 
		adj.edges[i][j] = w; 
		adj.edges[j][i] = w; 
	} 
	return(adj); 
} 
 
//------------------------------------------------------ 
 
graph Dijkstra(graph adj,char start,char end,int endnum) 
{ 
	int i,j; 
	for (i = 0; i < n; i++)				//对图进行必要的修改 
	{ 
		if(adj.vexs[i].name == start)	//起点置0 
			adj.vexs[i].num = 0; 
	} 
 
	while (adj.vexs[endnum].choose == false)	//终点未被圈定 
	{ 
		int temp=32767,min; 
		for (i = 0; i < n; i++)					//遍历所有顶点 
		{ 
			while (adj.vexs[i].choose == false)	//未圈定顶点中 
			{ 
				if(adj.vexs[i].num < temp)		//取总权值最小的顶点 
				{ 
					temp = adj.vexs[i].num; 
					min = i; 
				} 
				break; 
			} 
		} 
		adj.vexs[min].choose = true ;			//圈定权值最小的顶点 
 
		for (j = 0; j < n; j++)					//遍历所有顶点 
		{ 
			while (adj.vexs[j].choose == false)	//未圈定顶点中 
			{ 
				if (adj.edges[min][j] != -1)	//和当前最小权值顶点间存在线路 
				{ 
					if (adj.vexs[j].num > adj.edges[min][j] + adj.vexs[min].num) 
					//if(XXX)则修改顶点权值并前驱设为当前圈定顶点 
					{ 
						adj.vexs[j].num = adj.edges[min][j] + adj.vexs[min].num; 
						adj.vexs[j].pre = adj.vexs[min].name; 
					} 
				} 
				break ; 
			} 
		} 
	} 
	return(adj); 
} 
 
//------------------------------------------------------ 
 
void PrintPath(graph adj,char start,char end) 
{ 
	int i,endnum; 
	for (i = 0; i < n; i++)		//找出终点的顶点号 
	{ 
		if(adj.vexs[i].name == end) 
		{ 
			endnum = i; 
			break; 
		} 
	} 
 
	if (adj.vexs[endnum].pre != start) 
	{ 
		printf("%c<-",adj.vexs[endnum].pre); 
		PrintPath(adj,start,adj.vexs[endnum].pre);	//递归输出所有经过的节点 
	} 
 
} 
 
//------------------------------------------------------ 
 
void main() 
{ 
	int i,j,endnum; 
	graph adj0,adj1; 
	char start,end; 
 
	adj0 = adj1 = CreatGraph(); 
 
L2:	adj0 = adj1; 
	printf("\n请输入所求路径的起点:"); 
	start = getche(); 
	printf("\n请输入所求路径的终点:"); 
	end = getche(); 
	i=0; 
	while(i < n && adj0.vexs[i].name != start) 
		i++; 
	if (i >= n) 
	{ 
		printf("\n输入的起点不存在,请重新输入!\n"); 
		goto L2; 
	} 
	j=0; 
	while(j < n && adj0.vexs[j].name != end) 
		j++; 
	if (j >= n) 
	{ 
		printf("\n输入的终点不存在,请重新输入!\n"); 
		goto L2; 
	} 
	if (start == end) 
	{ 
		printf("\n起点与终点相同!\n"); 
		goto L2; 
	} 
 
	for (i = 0; i < n; i++)		//找出终点的顶点号 
	{ 
		if(adj0.vexs[i].name == end) 
		{ 
			endnum = i; 
			break; 
		} 
	} 
 
	adj0 = Dijkstra(adj0,start,end,endnum); 
 
	printf("\n最短路径为:"); 
	printf("%c<-",end); 
	PrintPath(adj0,start,end); 
	printf("%c",start); 
	printf("\n路径长度为%d\n",adj0.vexs[endnum].num); 
 
//	getch(); 
goto L2; 
}