main.cpp

给出实际的例子实现两个城市之间的最段路径.可以作为路径探索方面的参考.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define MAX_NAME 20
#define MAX_INFO 200
typedef int VRType;
typedef char VertexType[MAX_NAME];
#define INFINITY 65535
#define MAX_VERTEX_NUM 50

typedef struct 
{
	VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

struct MGraph
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum;
	int arcnum;
};

typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

//返回顶点在图中的序号
int LocateVex(MGraph G,VertexType u)
{
	int i;
	for(i =0; i< G.vexnum;i++)
	{
		if(strcmp(u,G.vexs[i]) == 0)
			return i;
	}
	return -1;
}
//read the file for creating the MGraph 
int CreateDN(MGraph &G)
{
	FILE *fp;
	char start_city_name[MAX_NAME];
	char end_city_name[MAX_NAME];
	int  distance_of_city = 0;
	
	fp=fopen("./ukcities.txt","r");
	
	//init MGraph data

	//顶点数量
	G.vexnum = 0;

	//初始化两点之间的弧长信息,在这里即为两个城市间的距离
	//INFINITY在这里应当理解为无穷大的意思,65535只是一个参考值
	for(int p=0;p<MAX_VERTEX_NUM;++p)
		for(int k=0;k<MAX_VERTEX_NUM;++k)
			G.arcs[p][k].adj = INFINITY;

	for(p=0;p<MAX_VERTEX_NUM;++p)
		strcpy(G.vexs[p],"");

	int m = 0;
	for(int i=0;i<MAX_VERTEX_NUM;i++)
	{
		fscanf(fp,"%s",start_city_name);
		if(LocateVex(G,start_city_name) == -1)
		{
			strcpy(G.vexs[m++],start_city_name);
			G.vexnum++;
			//printf("City Name: %s\n", start_city_name);
		}
		fscanf(fp,"%s",end_city_name); 
		if(LocateVex(G,end_city_name) == -1)
		{
			strcpy(G.vexs[m++],end_city_name);
			G.vexnum++;
			//printf("City Name: %s\n", end_city_name);
		}
		fscanf(fp,"%d",&distance_of_city); 
		int iStart = LocateVex(G,start_city_name);
		int iEnd   = LocateVex(G,end_city_name);
		//两个城市间的距离
		G.arcs[iStart][iEnd].adj = distance_of_city;	
	}
	fclose(fp);
	return 1;
}

//最短路径的floyd算法实现
void ShortestPathByFloyd(MGraph G,DistancMatrix &D)
{
	int u,v,w;
	for(v=0;v<G.vexnum;v++)
	{
		for(w=0;w<G.vexnum;w++)
		{
			D[v][w] = G.arcs[v][w].adj;
		}
		
	}
	for(u=0;u<G.vexnum;u++)
	{	
		for(v=0;v<G.vexnum;v++)
		{	
			for(w=0;w<G.vexnum;w++)
			{	
				if(D[v][u] + D[u][w] < D[v][w])
				{
					D[v][w] = D[v][u] + D[u][w];
				}
			}
		}
	}
}
int GetTheShortestDistance(char  start_city[],char end_city[])
{
	MGraph g;
	CreateDN(g);
	int i;
	
	for(i=0;i<g.vexnum;i++)
	{
		g.arcs[i][i].adj = 0;
	}
	DistancMatrix d;
	ShortestPathByFloyd(g,d);
	int nStart	= LocateVex(g,start_city);
	int nEnd	= LocateVex(g,end_city);
	if(nStart == -1)
	{
		printf("This city is not exist:%s\n",start_city);
		return 0;
	}
	if(nEnd == -1)
	{
		printf("This city is not exist:%s\n",end_city);
		return 0;
	}

/*	
	int j;
	for(i=0;i<g.vexnum;i++)
	{
		for(j=0;j<g.vexnum;j++)
		{
			if(d[i][j] == INFINITY)
			{
				printf("* ");
			}
			else
			{
				printf("%02d ",g.arcs[i][j]);
			}
		}
		printf("\n");
	}

	
	for(i=0;i<g.vexnum;i++)
	{
		for(j=0;j<g.vexnum;j++)
		{
			if(d[i][j] == INFINITY)
			{
				printf("* ");
			}
			else
			{
				printf("%03d ",d[i][j]);
			}
		}
		printf("@\n");
	}
*/
	if(d[nStart][nEnd] == INFINITY)
	{
		return -1;
	}
	else
	{
		return d[nStart][nEnd];
	}
}
void main()
{
	int key;
	char start_city[MAX_NAME];
	char end_city[MAX_NAME];
	do
	{
		printf("Enter the start city name:\n");
		scanf("%s",start_city);

		printf("Enter the end city name:\n");
		scanf("%s",end_city);

		int nDistance = GetTheShortestDistance(start_city,end_city);

		if(nDistance == -1)
		{
			printf("Can't find the path from %s to %s\n",start_city,end_city);
		}
		else
		{
			printf("The shortest distance between %s and %s is %dkm\n",start_city,end_city,nDistance);
		}
		printf("Press 'y' or 'Y' to continue or any key to quit!\n");
	}
	while((key = getch()) == 'y' || key == 'Y');
	
}