router.cpp

Dijkstra最短路径算法

#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;
}