#include
#include
using?namespace?std;

			
//*******************圖的鄰接矩陣表示*************
typedef?struct
{
	char*vexs;		//頂點向量;
	int?**arcs;		//鄰接矩陣;
	int?vexnumarcnum;		//圖的當(dāng)前頂點數(shù)和弧數(shù);
}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;
}


//創(chuàng)建有向圖的鄰接矩陣存儲結(jié)構(gòu)
//此時.adj存儲弧的長度;
void?createMGraph（MGraph&mg）
{
	int?ij;
	ifstream?fin（“Floyd.txt“ios::in）;//文件流類對象
	if（!fin）//判斷文件流類對象是否創(chuàng)建成功
	{
		cout<<“文件無法打開！“<		exit（0）;
	}
	fin>>mg.vexnum>>mg.arcnum;//從文件輸入頂點數(shù)和邊數(shù)
	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];//標(biāo)志數(shù)組
	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;//記錄當(dāng)前距離最短的頂點
			}
		}
		final[k]=true;//表示已求出v0到k的最短距離
		//當(dāng)前最短路徑更新
		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算法//求有向網(wǎng)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??導(dǎo)航最短路徑查詢\
?????目錄???????????0??2014-06-07?23:53??導(dǎo)航最短路徑查詢\Debug\
?????文件???????74752??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\vc60.idb
?????文件??????118784??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\vc60.pdb
?????文件??????573538??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).exe
?????文件??????820400??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).ilk
?????文件??????355920??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).obj
?????文件?????2098908??2013-12-26?17:30??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).pch
?????文件?????1139712??2013-12-27?00:45??導(dǎo)航最短路徑查詢\Debug\導(dǎo)航最短路經(jīng).pdb
?????文件?????????119??2013-12-14?19:35??導(dǎo)航最短路徑查詢\Floyd.txt
?????文件??????????44??2013-12-04?21:14??導(dǎo)航最短路徑查詢\Floyd2.txt
?????文件????????5238??2013-12-26?17:35??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).cpp
?????文件????????3475??2013-12-27?00:45??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).dsp
?????文件?????????532??2013-12-27?00:46??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).dsw
?????文件???????41984??2013-12-27?00:46??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).ncb
?????文件???????48640??2013-12-27?00:46??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).opt
?????文件????????1192??2013-12-27?00:45??導(dǎo)航最短路徑查詢\導(dǎo)航最短路經(jīng).plg
?????文件??????153600??2014-06-07?23:53??數(shù)據(jù)結(jié)構(gòu)_導(dǎo)航最短路徑查詢課外實踐報告.doc