浙江大学数据结构课程（陈越）____数据结构作业

/***************************************************************************************
Dijkstra算法实现 
*****************************************************************************************/ 
#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 < Graph->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 < Graph->Nv; i++）
		for（j = 0; j < Graph->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 < Graph->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 < Graph->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 < Graph->Nv; V++）
			if（collectS[V] == false && Graph->G[minV][V] < INFINITY）
				if（Dist[minV] + Graph->G[minV][V] < Dist[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 < numV; V++）
		if（collectS[V] == false && Dist[V] < minDist）{
			minDist = Dist[V];
			minV = V;
		}
			
	return minV;
}

MGraph TestData（V

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-10-09 21:45  浙江大学数据结构课程（陈越）____数据结构作业
     目录           0  2018-01-04 09:24  浙江大学数据结构课程（陈越）____数据结构作业Dijkstra
     文件        3601  2018-01-04 09:24  浙江大学数据结构课程（陈越）____数据结构作业Dijkstraexample.c
     文件      160764  2018-01-04 09:24  浙江大学数据结构课程（陈越）____数据结构作业Dijkstraexample.exe
     目录           0  2017-12-26 16:20  浙江大学数据结构课程（陈越）____数据结构作业Huffman Codes
     文件       10929  2017-12-26 16:19  浙江大学数据结构课程（陈越）____数据结构作业Huffman Codesexample.c
     文件      169541  2017-12-26 16:20  浙江大学数据结构课程（陈越）____数据结构作业Huffman Codesexample.exe
     目录           0  2017-12-24 19:24  浙江大学数据结构课程（陈越）____数据结构作业HuffmannTreeBuild
     文件        3872  2017-12-24 19:25  浙江大学数据结构课程（陈越）____数据结构作业HuffmannTreeBuildexample.c
     文件      161691  2017-12-24 19:24  浙江大学数据结构课程（陈越）____数据结构作业HuffmannTreeBuildexample.exe
     目录           0  2017-12-21 19:38  浙江大学数据结构课程（陈越）____数据结构作业Root of AVL Tree
     文件        4177  2017-12-21 19:38  浙江大学数据结构课程（陈越）____数据结构作业Root of AVL Treeexample.c
     文件      160369  2017-12-21 19:38  浙江大学数据结构课程（陈越）____数据结构作业Root of AVL Treeexample.exe
     目录           0  2017-12-13 09:12  浙江大学数据结构课程（陈越）____数据结构作业一元多项式的乘法与加法运算
     文件        4547  2017-12-13 09:20  浙江大学数据结构课程（陈越）____数据结构作业一元多项式的乘法与加法运算example.c
     文件      161115  2017-12-13 09:12  浙江大学数据结构课程（陈越）____数据结构作业一元多项式的乘法与加法运算example.exe
     目录           0  2017-12-18 09:39  浙江大学数据结构课程（陈越）____数据结构作业两个有序链表序列的合并
     文件        2606  2017-12-12 11:22  浙江大学数据结构课程（陈越）____数据结构作业两个有序链表序列的合并example.c
     文件      159497  2017-12-18 09:39  浙江大学数据结构课程（陈越）____数据结构作业两个有序链表序列的合并example.exe
     目录           0  2017-12-22 08:39  浙江大学数据结构课程（陈越）____数据结构作业二叉搜索树的操作集
     文件        4988  2017-12-22 08:39  浙江大学数据结构课程（陈越）____数据结构作业二叉搜索树的操作集example.c
     文件      161624  2017-12-22 08:39  浙江大学数据结构课程（陈越）____数据结构作业二叉搜索树的操作集example.exe
     目录           0  2017-12-18 15:22  浙江大学数据结构课程（陈越）____数据结构作业二叉树的遍历
     文件        3481  2017-12-18 15:35  浙江大学数据结构课程（陈越）____数据结构作业二叉树的遍历example.c
     文件      161008  2017-12-18 15:22  浙江大学数据结构课程（陈越）____数据结构作业二叉树的遍历example.exe
     目录           0  2017-12-29 11:27  浙江大学数据结构课程（陈越）____数据结构作业列出连通集
     文件        5386  2017-12-29 11:26  浙江大学数据结构课程（陈越）____数据结构作业列出连通集example_LGraph.c
     文件      162107  2017-12-29 11:27  浙江大学数据结构课程（陈越）____数据结构作业列出连通集example_LGraph.exe
     文件        4940  2017-12-29 09:50  浙江大学数据结构课程（陈越）____数据结构作业列出连通集example_MGraph.c
     文件      162125  2017-12-29 09:54  浙江大学数据结构课程（陈越）____数据结构作业列出连通集example_MGraph.exe
     目录           0  2018-01-03 16:32  浙江大学数据结构课程（陈越）____数据结构作业哈利·波特的考试
............此处省略30个文件信息