数据结构导航最短路径查询课外实践

数据结构_导航最短路径查询课外实践，迪杰斯特拉算法 弗洛伊德算法

#include
#include
using namespace std;

			
//*******************图的邻接矩阵表示*************
typedef struct
{
	char*vexs;		//顶点向量;
	int **arcs;		//邻接矩阵;
	int vexnumarcnum;		//图的当前顶点数和弧数;
}MGraph;
//***********************************************
//***********查找u顶点在顶点向量中的位置*********
int locate（MGraph Gchar u）
{
	int i;
	int k;
	for（i=0;i	{
		if（u==G.vexs[i]）
		{
			k=i;
			break;
		}
	}
	return k;
}


//创建有向图的邻接矩阵存储结构
//此时.adj存储弧的长度;
void createMGraph（MGraph&mg）
{
	int ij;
	ifstream fin（“Floyd.txt“ios::in）;//文件流类对象
	if（!fin）//判断文件流类对象是否创建成功
	{
		cout<<“文件无法打开！“<		exit（0）;
	}
	fin>>mg.vexnum>>mg.arcnum;//从文件输入顶点数和边数
	mg.vexs=new char[mg.vexnum];//开辟空间存储各顶点
	for（ i=0;i	{
		fin>>mg.vexs[i];//从文件输入顶点
	}
	//*************开辟空间存储邻接矩阵*************
	mg.arcs=new int*[mg.vexnum];
	for（i=0;i	{
		mg.arcs[i]=new int[mg.vexnum];
	}
	//*****************end************************

	for（i=0;i	{
		for（j=0;j		{
			fin>>mg.arcs[i][j];
			cout<		}
		cout<	}
}
//************求v0到其余各顶点的最短距离及路径*****************

void ShortestPath_DIJ（MGraph&Gint v0int *&Pint*&D）
{
	int ikjmin;
	bool *final=new bool[G.vexnum];//标志数组
	P=new int [G.vexnum];//全局变量存储路径
	D=new int [G.vexnum];//全局变量存储最短距离
	//初始化;
	for（i=0;i	{
		final[i]=false;
		D[i]=G.arcs[v0][i];
		P[i]=v0;
	}

	final[v0]=true;//表示始点已求出最短路径;
	for（i=1;i	{
		//找一个顶点从v0到该顶点距离最短
		min=1000;//min初始化为最大值
		for（j=0;j		{
			if（!final[j]&&min>D[j]）
			{
				min=D[j];
				k=j;//记录当前距离最短的顶点
			}
		}
		final[k]=true;//表示已求出v0到k的最短距离
		//当前最短路径更新
		for（j=0;j		{
			if（!final[j]&&（min+G.arcs[k][j]）			{
				D[j]=G.arcs[k][j]+min;
				P[j]=k;
			}
		}
	}
}

//输出最短路径（递归算法）;//b到v0的路径
void explainPathRecursionDIJ（MGraph&Gint *pathint v0int b）
{
	int k;
	if（v0==b）
	{
		k=v0;
		cout<	}
	else
	{
		explainPathRecursionDIJ（Gpathpath[v0]b）;
		k=v0;
		cout<	}
}
//输出最短路径及长度;//b到其余各顶点的路径
void printPathDIJ（MGraph&Gint *pathint*dint b）
{
	int n=G.vexnum;
	int i;
	cout<<“始点“<<‘\t‘<<“终点“<<‘\t‘<<“最短路径“<<“\t“<<“路径长度“<	for（i=0;i	{
		if（i!=b）
		{
			cout<			explainPathRecursionDIJ（Gpathib）;
			cout<<“\t\t“<			cout<		}
	}
	cout<}



//Floyd算法//求有向网G中各对顶点v和w之间的最短路径
void ShortestPath_FLOYD（MGraph&Gint **&pint **&d）
{
	int ijk;
	//开辟空间存储最短路径与最短距离（p和d都是二维的）
	p=new int *[G.vexnum];
	d=new int *[G.vexnum];
	for（i=0;i	{
		p[i]=new int [G.vexnum];
		d[i]=new int [G.vexnum];
	}

	//初始化
	for（i=0;i	{
		for（j=0;j		{
			p[i][j]=i;//记录初始路径
			d[i][j]=G.arcs[i][j];//记录初始路径长度
		}
	}
	//求最短距离和最短路径
	for（k=0;k	{
		for（i=0

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-06-07 23:53  导航最短路径查询\
     目录           0  2014-06-07 23:53  导航最短路径查询\Debug\
     文件       74752  2013-12-27 00:45  导航最短路径查询\Debug\vc60.idb
     文件      118784  2013-12-27 00:45  导航最短路径查询\Debug\vc60.pdb
     文件      573538  2013-12-27 00:45  导航最短路径查询\Debug\导航最短路经.exe
     文件      820400  2013-12-27 00:45  导航最短路径查询\Debug\导航最短路经.ilk
     文件      355920  2013-12-27 00:45  导航最短路径查询\Debug\导航最短路经.obj
     文件     2098908  2013-12-26 17:30  导航最短路径查询\Debug\导航最短路经.pch
     文件     1139712  2013-12-27 00:45  导航最短路径查询\Debug\导航最短路经.pdb
     文件         119  2013-12-14 19:35  导航最短路径查询\Floyd.txt
     文件          44  2013-12-04 21:14  导航最短路径查询\Floyd2.txt
     文件        5238  2013-12-26 17:35  导航最短路径查询\导航最短路经.cpp
     文件        3475  2013-12-27 00:45  导航最短路径查询\导航最短路经.dsp
     文件         532  2013-12-27 00:46  导航最短路径查询\导航最短路经.dsw
     文件       41984  2013-12-27 00:46  导航最短路径查询\导航最短路经.ncb
     文件       48640  2013-12-27 00:46  导航最短路径查询\导航最短路经.opt
     文件        1192  2013-12-27 00:45  导航最短路径查询\导航最短路经.plg
     文件      153600  2014-06-07 23:53  数据结构_导航最短路径查询课外实践报告.doc