#include?“StdAfx.h“
#include?“Algorithm.h“
///////////////////////////////////////////////////////////
////打開文件，存儲圖為AG，若打開失敗則返回false
///////////////////////////////////////////////////////////
bool?CreateGraph（Graph*?AG?char*?filePath）
{
	FILE*?fp;
	fp?=?fopen（filePath?“r“）;
	if?（fp?==?NULL）
	{
		return?false;
	}
	fscanf（fp?“%d%d\n“?&AG->vertex?&AG->edge）;//記錄頂點數(shù)n、邊數(shù)e
	int?a?b;
	double?c;
	AG->length?=?new?double*[AG->vertex?+?1];
	AG->connect?=?new?int*[AG->vertex?+?1];
	AG->adjoin?=?new?vector[AG->vertex?+?1];
	AG->inGraph?=?new?int[AG->vertex?+?1];
	for?（int?i?=?0;?i?<=?AG->vertex;?i++）		//權矩陣初始化
	{
		AG->length[i]?=?new?double[AG->vertex?+?1];
		AG->connect[i]?=?new?int[AG->vertex?+?1];
		AG->inGraph[i]?=?0;
		for?（int?j?=?0;?j?<=?AG->vertex;?j++）
		{
			if?（i?==?j）
				AG->length[i][j]?=?0;
			else
				AG->length[i][j]?=?Infinite_Length;
			AG->connect[i][j]?=?0;
		}
	}
	while?（fscanf（fp?“%d?%d?%lf\n“&a?&b?&c）?!=?EOF）//無向圖
	{
		AG->length[a][b]?=?c;
		AG->length[b][a]?=?c;
		AG->inGraph[a]?=?1;
		AG->inGraph[b]?=?1;
		AG->adjoin[a].push_back（b）;
		AG->adjoin[b].push_back（a）;
		AG->connect[a][b]?=?1;
		AG->connect[b][a]?=?1;
	}
	return?true;
}
////////////////////////////////////////////////////////////
///////////是否已選取過每一個點//////////////////////////////
///////////////////////////////////////////////////////////
bool?allPicked（int?arr[]?int?n）	
{
	for?（int?i?=?0;?i?<=?n;?i++）
	{
		if?（arr[i]??==?0）
			return?false;
		else
			continue;
	}
	return?true;
}
///////////////////////////////////////////////////////////
///////Dijkstra算法；path用于存儲最短路徑////////////////////
///////////////////////////////////////////////////////////
double?Dijkstra（Graph*?AG?int?origin?int?path[]）	
{
	int*?S?=?new?int[AG->vertex?+?1];		//標記圖中的點，若已找到距離原點最短路徑，則標記為1，否則為0
	double*?path_length?=?new?double[AG->vertex?+?1];????//記錄各點到達原點的最短距離

	for?（int?i?=?0;?i?<=?AG->vertex;?i++）
	{
		S[i]?=??0;	//S初始化為0
		path_length[i]?=?Infinite_Length;	//最短距離初始化為無窮大
		path[i]?=?origin;
	}
	S[origin]?=?1;		//原點標記為1
	path_length[origin]?=?0;
	for（int?i?=?0;?i?<=?AG->vertex;?i++）??//令path_length為各點到原點距離
	{
		path_length[i]?=?AG->length[origin][i];
	}
	int?j?=?0;
	double?min_length?=?Infinite_Length;	//最短路徑長
	int?count?=?AG->vertex?+?1;
	while（count）
	{
		count--;
		min_length?=?Infinite_Length;
		for?（int?i?=?0;?i?<=?AG->vertex;?i++）?//求minPi（i）
		{
			if?（S[i]?==?1）
				continue;
			if?（path_length[i]?			{
				j?=?i;
				min_length?=?path_length[i];
			}
		}
		S[j]?=?1;	//標記找到最短路徑的點
		if?（allPicked（S?AG->vertex））	//如果所有點都已標記
			break;
		for?（int?i?=?0;?i?<=?AG->vertex;?i++）?//對所有與j相連的節(jié)點
		{
			if?（S[i]?==?1）
				continue;
			if?（path_length[i]?>?min_length?+?AG->length[i][j]）??//求min（Pi（i）?Pi（j）?+?wij）
			{
				path_length[i]?=?min_length?+?AG->length[i][j];
				path[i]?=?j;
			}
		}
	}
	return?0;
}
////////////////////////////////////////////

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????294400??2013-01-09?10:49??圖論算法大全\bin\GraphTest.exe

?????文件????6073344??2013-01-09?10:49??圖論算法大全\bin\GraphTest.pdb

?????文件????3854326??2012-09-07?21:35??圖論算法大全\bin\graph_movie.txt

?????文件????3854326??2012-09-07?21:35??圖論算法大全\graph_movie.txt

?????文件????????891??2012-12-03?23:03??圖論算法大全\ShortCut.sln

????..A..H.?????43008??2013-01-16?20:40??圖論算法大全\ShortCut.suo

?????文件??????17172??2013-01-16?20:29??圖論算法大全\src\Algorithm.cpp

?????文件???????2377??2013-01-07?13:10??圖論算法大全\src\Algorithm.h

?????文件???????4354??2012-12-17?00:08??圖論算法大全\src\BetweenCen.cpp

?????文件????????653??2012-12-11?15:04??圖論算法大全\src\BetweenCen.h

?????文件????????502??2012-12-07?23:50??圖論算法大全\src\CDialog.cpp

?????文件????????354??2012-12-07?23:41??圖論算法大全\src\CDialog.h

?????文件???????4323??2012-12-17?00:08??圖論算法大全\src\CloseCen.cpp

?????文件????????770??2012-12-11?15:10??圖論算法大全\src\CloseCen.h

?????文件???????2093??2013-01-07?20:25??圖論算法大全\src\ConnectX.cpp

?????文件????????595??2013-01-07?20:20??圖論算法大全\src\ConnectX.h

?????文件???????2116??2013-01-09?10:49??圖論算法大全\src\ConnectY.cpp

?????文件????????595??2013-01-07?20:25??圖論算法大全\src\ConnectY.h

?????文件???????2576??2013-01-07?20:10??圖論算法大全\src\KruskalTree.cpp

?????文件????????627??2013-01-07?20:10??圖論算法大全\src\KruskalTree.h

?????文件???????1741??2013-01-07?20:20??圖論算法大全\src\PrimDialog.cpp

?????文件????????598??2013-01-06?18:42??圖論算法大全\src\PrimDialog.h

?????文件???????3160??2012-12-03?23:03??圖論算法大全\src\ReadMe.txt

?????文件??????67777??2009-08-31?02:31??圖論算法大全\src\res\ShortCut.ico

?????文件????????672??2012-12-03?23:03??圖論算法大全\src\res\ShortCut.rc2

?????文件???????4476??2013-01-07?13:30??圖論算法大全\src\resource.h

?????文件?????110000??2013-01-07?20:25??圖論算法大全\src\ShortCut.aps

?????文件???????2019??2012-12-03?23:03??圖論算法大全\src\ShortCut.cpp

?????文件????????454??2012-12-03?23:03??圖論算法大全\src\ShortCut.h

?????文件??????19954??2013-01-07?20:25??圖論算法大全\src\ShortCut.rc

............此處省略15個文件信息