citymap.cpp

数据结构的经典实验程序。以全国主要城市为图的顶点, 铁路连接为图的边, 距离作为加权, 设计完成一个最短路径自动查找系统；输入为出发城市和目标城市, 输出为最短路径和距离。

// Citymap.cpp: implementation of the CCitymap class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Dijkstra_TA.h"
#include "Citymap.h"

//#include "City.h"	// Added by ClassView

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#ifndef N
#define N 15
#endif
#ifndef NoEdge
#define NoEdge 65535
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


CCitymap::CCitymap()
{
	//以13个城市为依据，建立初始的邻接矩阵 和城市列表
	/*0	北京
	1	哈尔滨
	2	呼和浩特
	3	乌鲁木齐
	4	上海
	5	郑州
	6	长沙
	7	广州
	8	福州
	9	南京
	10	西安
	11	兰州
	12	重庆
	13  长春
	14  南昌*/
	m_ChinaMainCity[0].pointx=540;
	m_ChinaMainCity[0].pointy=214;

	m_ChinaMainCity[1].pointx=654;
	m_ChinaMainCity[1].pointy=120;

	m_ChinaMainCity[2].pointx=483;
	m_ChinaMainCity[2].pointy=200;

	m_ChinaMainCity[3].pointx=214;
	m_ChinaMainCity[3].pointy=142;

	m_ChinaMainCity[4].pointx=612;
	m_ChinaMainCity[4].pointy=341;

	m_ChinaMainCity[5].pointx=511;
	m_ChinaMainCity[5].pointy=297;

	m_ChinaMainCity[6].pointx=503;
	m_ChinaMainCity[6].pointy=395;

	m_ChinaMainCity[7].pointx=513;
	m_ChinaMainCity[7].pointy=468;

	m_ChinaMainCity[8].pointx=590;
	m_ChinaMainCity[8].pointy=423;

	m_ChinaMainCity[9].pointx=579;
	m_ChinaMainCity[9].pointy=331;

	m_ChinaMainCity[10].pointx=448;
	m_ChinaMainCity[10].pointy=300;

	m_ChinaMainCity[11].pointx=389;
	m_ChinaMainCity[11].pointy=277;

	m_ChinaMainCity[12].pointx=416;
	m_ChinaMainCity[12].pointy=368;

	m_ChinaMainCity[13].pointx=640;
	m_ChinaMainCity[13].pointy=148;

	m_ChinaMainCity[14].pointx=551;
	m_ChinaMainCity[14].pointy=383;

	//m_ChinaMainCity[0].pointx=;
	//m_ChinaMainCity[0].pointy=;
/////////////////////////
	int i=0,j=0;
	for(i=0 ;i<N;i++)
		for(j=0;j<N;j++)
			m_road_city[i][j]=NoEdge;//NoEdge表示城市间没有直接的连线

////////根据实际距离初始化邻接矩阵
	//m_road_city[0][1]=1288;
	
	m_road_city[0][2]=667;
	m_road_city[0][5]=689;
	m_road_city[0][9]=1160;
	m_road_city[0][13]=1046;
	
	m_road_city[1][13]=242;
	m_road_city[2][3]=3036;
	m_road_city[3][11]=1892;

	//m_road_city[4][6]=1207;
	m_road_city[4][8]=1180;
	m_road_city[4][9]=303;
	m_road_city[4][14]=825;

	m_road_city[5][6]=898;
	m_road_city[5][9]=695;
	m_road_city[5][10]=511;

	m_road_city[6][7]=707;
	m_road_city[6][12]=1419; 
	m_road_city[6][14]=482; 

	m_road_city[7][8]=1588;
	m_road_city[10][11]=676;
	m_road_city[10][12]=1346;
//	m_road_city[][]=;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			if(m_road_city[i][j]!=NoEdge)m_road_city[j][i]=m_road_city[i][j];
}

CCitymap::~CCitymap()
{

}
//int road[15][15], int kay[15][15])
void CCitymap::Allroad()
{
	//起点城市和目的城市对应于算法中的i，j
	//初始化 c(i,j,o)
/*//DEL	int i,j,k;
	for(i =0; i<N;i++)
		for(j=0;j<N;j++){
		m_road[i][j]=m_road_city[i][j];
		m_kay[i][j]=0;
		}
	for(i=0;i<N;i++)
		m_road[i][i]=NoEdge;

	//计算road[i][j]=c(i,j,k)
	//从i到j的路径中，最大的点序号是k
	int temproad1=0,temproad2=0,temproad3=0;
	for(k=0;k<N;k++)
		for(i=0;i<N;i++)
			for(j=0;j<N;j++){
			temproad1=m_road[i][k];
			temproad2=m_road[k][j];
			temproad3=m_road[i][j];
			if(temproad1!=-1&&temproad2!=-1&&(temproad3==-1||temproad1+temproad2<temproad3)){
				m_road[i][j]=temproad1+temproad2;
				m_kay[i][i]=k;
			}
			}*///DEL
}

void CCitymap::OutputRoad(int i, int j,int travel[])
{	
/*//DEL	if(i==j)return;
	if(m_kay[i][j]==0){*(travel++)=j;}
	else{
		OutputRoad(i,m_kay[i][j],travel);
		OutputRoad(m_kay[i][j],j,travel);
	} *///DEL

}

void CCitymap::Travel(int i, int j, int travel[])
{	
	//if(m_road[i][j]>32767)
		//return;
/*///DEL	travel[0]=i;
	travel[1]=5;
	travel[2]=10;
	travel[3]=12;/*///DEL
	//OutputRoad(i,j,travel);



}

// Dijkstra最短路径算法
void CCitymap::ShortPath(int travel[], int start, int goal)
{
	//
	int min=NoEdge;
	int v;
	bool final[N];
	int distance[N];
	int path[N];
	//initialization
	int i=0, j=0;
	if(start==-1||goal==-1)
		return;
	for(i=0;i<N;i++){
		final[i]=false;
		distance[i]=m_road_city[start][i];
		if(distance[i]<min)path[i]=start;
	}
	final[start]=true;//immune loop
	//dijkstra arithmetic
	for(i=0;i<N;i++){
		min=NoEdge;
		for(j=0;j<N;j++){// find the minimum distance then start with the minimum v point
			if(!final[j])
				if(distance[j]<min){
					min=distance[j];
					v=j;
				} //if
		}//for_j
		final[v]=true;
		for(int k=0;k<N;k++){ 
			if(!final[k]&&(min+m_road_city[v][k]<distance[k])){
				distance[k]=min+m_road_city[v][k];
				path[k]=v;
			}//if	
		}//for_j
		
	}//for_i

	//put the path into travel using order
	int temppath=goal;
	travel[0]=goal;
	for(j=1;temppath!=start&&j<N;j++){
		temppath=path[temppath];
		travel[j]=temppath;
	//path[]
	}
}