#include“Dijkstra.h“
#include
using?namespace?std;

Dijkstra::Dijkstra（）
{

}

void?Dijkstra::DijkstraA（int?n?int?v?int?*dist?int?*prev?int?c[maxnum][maxnum]）
{
	bool?s[maxnum];????//?判斷是否已存入該點到S集合中
	for（int?i=1;?i<=n;?++i）
	{
		dist[i]?=?c[v][i];
		s[i]?=?0;?????//?初始都未用過該點
		if（dist[i]?==?maxint）
			prev[i]?=?0;
		else
			prev[i]?=?v;
	}
	dist[v]?=?0;
	s[v]?=?1;
?
	//?依次將未放入S集合的結(jié)點中，取dist[]最小值的結(jié)點，放入結(jié)合S中
	//?一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長度
?????????//?注意是從第二個節(jié)點開始，第一個為源點
	for（int?i=2;?i<=n;?++i）
	{
		int?tmp?=?maxint;
		int?u?=?v;
		//?找出當前未使用的點j的dist[j]最小值
		for（int?j=1;?j<=n;?++j）
			if（（!s[j]）?&&?dist[j]			{
				u?=?j;??????????????//?u保存當前鄰接點中距離最小的點的號碼
				tmp?=?dist[j];
			}
		s[u]?=?1;????//?表示u點已存入S集合中
?
		//?更新dist
		for（int?j=1;?j<=n;?++j）
			if（（!s[j]）?&&?c[u][j]			{
				int?newdist?=?dist[u]?+?c[u][j];
				if（newdist?				{
					dist[j]?=?newdist;
					prev[j]?=?u;
				}
			}
	}
}

QString?Dijkstra::searchPath（int?numint?*prevint?v?int?u）
{
	QString?path=““;

	int?que[maxnum];
	int?tot?=?1;
	que[tot]?=?u;
	tot++;
	int?tmp?=?prev[u];
	while（tmp?!=?v）
	{
		que[tot]?=?tmp;
		tot++;
		tmp?=?prev[tmp];
	}
	que[tot]?=?v;
	int?j=0;
	for（int?i=tot;?i>=1;?--i）
	{
		if（i?!=?1）
		{
			for（int?k=0;k			{
				if（que[i]==All[k]）
				{
					path+=CityName[k]+“->“;
				}
			}
		}
		else
		{
			for（int?k=0;k			{
				if（que[i]==All[k]）
				{
					path+=CityName[k];
				}
			}
		}
	}
	return?path;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-06-23?23:26??Project3_01\
?????目錄???????????0??2013-06-23?22:25??Project3_01\ipch\
?????目錄???????????0??2013-06-23?23:26??Project3_01\ipch\project3_01-d6ad722\
?????文件????51052544??2013-06-23?23:26??Project3_01\ipch\project3_01-d6ad722\project3_01-bd672456.ipch
?????目錄???????????0??2013-06-21?17:15??Project3_01\Project3_01\
?????文件????22106112??2013-06-23?23:26??Project3_01\Project3_01.sdf
?????文件?????????900??2013-06-19?00:07??Project3_01\Project3_01.sln
?????文件???????24064??2013-06-23?23:26??Project3_01\Project3_01.suo
?????目錄???????????0??2013-06-23?23:26??Project3_01\Project3_01\Debug\
?????文件???????18484??2013-06-23?23:15??Project3_01\Project3_01\Debug\cl.command.1.tlog
?????文件??????333904??2013-06-23?23:15??Project3_01\Project3_01\Debug\CL.read.1.tlog
?????文件???????18142??2013-06-23?23:15??Project3_01\Project3_01\Debug\CL.write.1.tlog
?????文件????????7890??2013-06-23?22:55??Project3_01\Project3_01\Debug\custombuild.command.1.tlog
?????文件????????1808??2013-06-23?22:55??Project3_01\Project3_01\Debug\custombuild.read.1.tlog
?????文件????????3230??2013-06-23?22:55??Project3_01\Project3_01\Debug\custombuild.write.1.tlog
?????文件???????77506??2013-06-23?23:15??Project3_01\Project3_01\Debug\Dijkstra.obj
?????文件???????25598??2013-06-23?20:09??Project3_01\Project3_01\Debug\Floyd.obj
?????文件???????25857??2013-06-20?18:13??Project3_01\Project3_01\Debug\Graph.obj
?????文件????????7640??2013-06-23?23:15??Project3_01\Project3_01\Debug\link.command.1.tlog
?????文件???????13498??2013-06-23?23:15??Project3_01\Project3_01\Debug\link.read.1.tlog
?????文件????????4880??2013-06-23?23:15??Project3_01\Project3_01\Debug\link.write.1.tlog
?????文件???????75128??2013-06-23?23:15??Project3_01\Project3_01\Debug\main.obj
?????文件???????77950??2013-06-23?23:15??Project3_01\Project3_01\Debug\moc_project3_01.obj
?????文件????????1690??2013-06-23?23:15??Project3_01\Project3_01\Debug\mt.command.1.tlog
?????文件????????3698??2013-06-23?23:15??Project3_01\Project3_01\Debug\mt.read.1.tlog
?????文件????????1132??2013-06-23?23:15??Project3_01\Project3_01\Debug\mt.write.1.tlog
?????文件?????????381??2013-06-23?23:15??Project3_01\Project3_01\Debug\Project3_01.exe.intermediate.manifest
?????文件??????????95??2013-06-23?23:26??Project3_01\Project3_01\Debug\Project3_01.lastbuildstate
?????文件????????1047??2013-06-23?23:26??Project3_01\Project3_01\Debug\Project3_01.log
?????文件??????348104??2013-06-23?23:15??Project3_01\Project3_01\Debug\project3_01.obj
?????文件???????18545??2013-06-22?02:21??Project3_01\Project3_01\Debug\qrc_project3_01.obj
............此處省略25個文件信息