/***************************************************************************************
Dijkstra算法實(shí)現(xiàn)?
*****************************************************************************************/?
#include?
#include?
#include?

#define?MaxNumVertex?500
#define?INFINITY?????65535
#define?ERROR????????-1
/*?define?edge?*/
typedef?int??VertexType;
typedef?int??WeightType;
typedef?int??CostType;
typedef?char?DataType;
typedef?struct?ENode?*PtrToENode;
struct?ENode{
	VertexType?V1?V2;
	WeightType?Weight;
};
typedef?PtrToENode?Edge;
/*?define?graph?and?func*/
typedef?struct?GNode?*PtrToGNode;
struct?GNode{
	int?Nv;
	int?Ne;
	WeightType?G[MaxNumVertex][MaxNumVertex];
	DataType?Data[MaxNumVertex];
};
typedef?PtrToGNode?MGraph;

MGraph?BuildMGraph（VertexType?*S）;
void?InsertEdge（MGraph?Graph?Edge?E）;
void?Dijkstra（MGraph?Graph?WeightType?*Dist?VertexType?*Path?VertexType?S）;
VertexType?FindMinValue（WeightType?*Dist?int?numV?bool?*collectS）;
/*?test?data?*/
MGraph?TestData（VertexType?*S）;

int?main（）
{
	MGraph?Graph;
	WeightType?Dist[MaxNumVertex];
	VertexType?Path[MaxNumVertex]?S?minVertex?V;
	
//	Graph?=?BuildMGraph（&S）;
	Graph?=?TestData（&S）;
	Dijkstra（Graph?Dist?Path?S）;
	for（V?=?0;?V?Nv;?V++）
		printf（“%d?“?Dist[V]）;
	
	return?0;
}

MGraph?BuildMGraph（VertexType?*S）
{
	int?i?j;
	MGraph?Graph;
	Edge?E;
	
	Graph?=?（MGraph）malloc（sizeof（struct?GNode））;
	E?=?（Edge）malloc（sizeof（struct?ENode））;
	scanf（“%d“?&Graph->Nv）;
	Graph->Ne?=?0;
	for（i?=?0;?i?Nv;?i++）
		for（j?=?0;?j?Nv;?j++）{
			if（i?==?j）
				Graph->G[i][j]?=?0;
			else?
				Graph->G[i][j]?=?INFINITY;
		}
	scanf（“%d?%d“?&Graph->Ne?S）;
	for（i?=?0;?i?Ne;?i++）{
		scanf（“%d?%d?%d“?&E->V1?&E->V2?&E->Weight）;
		InsertEdge（Graph?E）;
	}
	free（E）;
			
	return?Graph;
}

void?InsertEdge（MGraph?Graph?Edge?E）
{
	Graph->G[E->V1][E->V2]?=?E->Weight;
	Graph->G[E->V2][E->V1]?=?E->Weight;
}

void?Dijkstra（MGraph?Graph?WeightType?*Dist?VertexType?*Path?VertexType?S）
{
	VertexType?V?minV;
	bool?collectS[MaxNumVertex];
	/*?initial?the?Dist?and?Path?*/
	for（V?=?0;?V?Nv;?V++）{
		Dist[V]?=?Graph->G[S][V];
		Path[V]?=?S;
		collectS[V]?=?false;?
	}
	/*?do?the?Dijkstra?*/
	while（1）{
		minV?=?FindMinValue（Dist?Graph->Nv?collectS）;
		if（minV?==?ERROR）	
			break;
		collectS[minV]?=?true;
		for（V?=?0;?V?Nv;?V++）
			if（collectS[V]?==?false?&&?Graph->G[minV][V]?				if（Dist[minV]?+?Graph->G[minV][V]?					Dist[V]?=?Dist[minV]?+?Graph->G[minV][V];
					Path[V]?=?minV;
				}
	}
}

VertexType?FindMinValue（WeightType?*Dist?int?numV?bool?*collectS）
{
	VertexType?minV?V;
	WeightType?minDist;
	
	minDist?=?INFINITY;
	minV?=?ERROR;
	for（V?=?0;?V?		if（collectS[V]?==?false?&&?Dist[V]?			minDist?=?Dist[V];
			minV?=?V;
		}
			
	return?minV;
}

MGraph?TestData（V

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-10-09?21:45??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\
?????目錄???????????0??2018-01-04?09:24??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Dijkstra\
?????文件????????3601??2018-01-04?09:24??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Dijkstra\example.c
?????文件??????160764??2018-01-04?09:24??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Dijkstra\example.exe
?????目錄???????????0??2017-12-26?16:20??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Huffman?Codes\
?????文件???????10929??2017-12-26?16:19??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Huffman?Codes\example.c
?????文件??????169541??2017-12-26?16:20??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Huffman?Codes\example.exe
?????目錄???????????0??2017-12-24?19:24??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\HuffmannTreeBuild\
?????文件????????3872??2017-12-24?19:25??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\HuffmannTreeBuild\example.c
?????文件??????161691??2017-12-24?19:24??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\HuffmannTreeBuild\example.exe
?????目錄???????????0??2017-12-21?19:38??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Root?of?AVL?Tree\
?????文件????????4177??2017-12-21?19:38??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Root?of?AVL?Tree\example.c
?????文件??????160369??2017-12-21?19:38??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\Root?of?AVL?Tree\example.exe
?????目錄???????????0??2017-12-13?09:12??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\一元多項(xiàng)式的乘法與加法運(yùn)算\
?????文件????????4547??2017-12-13?09:20??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\一元多項(xiàng)式的乘法與加法運(yùn)算\example.c
?????文件??????161115??2017-12-13?09:12??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\一元多項(xiàng)式的乘法與加法運(yùn)算\example.exe
?????目錄???????????0??2017-12-18?09:39??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\兩個(gè)有序鏈表序列的合并\
?????文件????????2606??2017-12-12?11:22??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\兩個(gè)有序鏈表序列的合并\example.c
?????文件??????159497??2017-12-18?09:39??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\兩個(gè)有序鏈表序列的合并\example.exe
?????目錄???????????0??2017-12-22?08:39??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\二叉搜索樹的操作集\
?????文件????????4988??2017-12-22?08:39??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\二叉搜索樹的操作集\example.c
?????文件??????161624??2017-12-22?08:39??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\二叉搜索樹的操作集\example.exe
?????目錄???????????0??2017-12-18?15:22??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\二叉樹的遍歷\
?????文件????????3481??2017-12-18?15:35??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\二叉樹的遍歷\example.c
?????文件??????161008??2017-12-18?15:22??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\二叉樹的遍歷\example.exe
?????目錄???????????0??2017-12-29?11:27??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\列出連通集\
?????文件????????5386??2017-12-29?11:26??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\列出連通集\example_LGraph.c
?????文件??????162107??2017-12-29?11:27??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\列出連通集\example_LGraph.exe
?????文件????????4940??2017-12-29?09:50??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\列出連通集\example_MGraph.c
?????文件??????162125??2017-12-29?09:54??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\列出連通集\example_MGraph.exe
?????目錄???????????0??2018-01-03?16:32??浙江大學(xué)數(shù)據(jù)結(jié)構(gòu)課程（陳越）____數(shù)據(jù)結(jié)構(gòu)作業(yè)\哈利·波特的考試\
............此處省略30個(gè)文件信息