并行Dijkstra最短路径算法

并行Dijkstra最短路径算法，附有测试文件

/**输入邻接矩阵和源顶点，求最短路径。输入邻接矩阵中，位置（xy）为顶点y到x的边权**/
#include 
#include 
#include 
#include 

/**定义M为无穷大**/
#define M 1.7e308

#define BOOL int
#define FALSE 0
#define TRUE  1
#define W（xy） W[x*nodenum+y]

FILE* fp;
char ch;
char id[20];
int point;
double* W;
double* dist;
BOOL* bdist;
int nodenum = 0;
int S = 0;

/* show err and exit*/
void fatal（char* err）
{
	printf（“%s/n“ err）;
	exit（0）;
}

/**从文件中读取字符**/
void GetChar（）
{
	fread（&chsizeof（char）1fp）;
}

/**读取一个小数，如果为字符M或m，令其值为无穷大**/
double GetNextNum（）
{
	double num;

	while（!isdigit（ch） && ch!=‘M‘ && ch!=‘m‘）
		GetChar（）;

	if（isdigit（ch））
	{
		point = 0;
		while（isdigit（ch））
		{
			id[point] = ch;
			point ++;
			GetChar（）;
		}
		id[point] = 0;
		num = atof（id）;
	}else{
		num = M;
		GetChar（）;
	}
	return num;
}


/**读入邻接矩阵**/
void ReadMatrix（）
{
	char file[40];
	int ij;
	double num;

	printf（“Begin to read the matrix!\n“）;
	printf（“The first integer of the file should be the size of the matrix!\n“）;
	printf（“Input the file name of the matrix:“）;
	scanf（“%s“file）;

	if（（fp = fopen（file“r“）） == NULL）
	{
		fatal（“File name input error!“）;
	}
	num = GetNextNum（）;
	if（num < 0 || num > 10000）
	{
		fclose（fp）;
		fatal（“The matrix row input error!“）;
	}
	nodenum = （int）num;
	printf（“Input the start node:“）;
	scanf（“%d“&S）;
	if（S >= nodenum） fatal（“The start node input too big!\n“）;

	W = （double*）malloc（sizeof（double）*num*num）;
	if（ W == NULL）
	{
		fclose（fp）;
		fatal（“Dynamic allocate space for matrix fail!“）;
	}
	for（i=0;i		for（j=0;j		{
			W（ij） = GetNextNum（）;
		}
	fclose（fp）;
	printf（“Finish reading the matrixthe nodenum is: %d;\n“nodenum）;
}

/**各处理器数据初始化**/
void Init（int my_rankint group_sizeint ep）
{
	int i;
	MPI_Status status;
	if（my_rank == 0）
	{
		for（i=1;i		{
			MPI_Send（&W（ep*（i-1）0）ep*nodenumMPI_DOUBLEiiMPI_COMM_WORLD）;//向各个处理器传送所需要的邻接矩阵块 
		}
	}else{
		dist = （double*）malloc（sizeof（double）*ep）;
		bdist = （int*） malloc（sizeof（BOOL）*ep）;
		W = （double*）malloc（sizeof（double）*ep*nodenum）;
		if（W == NULL || dist == NULL || bdist == NULL）
			fatal（“Dynamic allocate space for matrix fail!“）;
		MPI_Recv（Wep*nodenumMPI_DOUBLE0my_rankMPI_COMM_WORLD&status）;//接收各自所需要的邻接矩阵块 
		/*
		初始化dist和bdist 
		*/
		for（i=0;i		{
			if（i+（my_rank-1）*ep == S）
			{
				dist[i] = 0;
				bdist[i] = TRUE;
			}else{
				dist[i] = W（iS）;
				bdist[i] = FALSE;
			}
		}
	}
}


/**输出邻接矩阵**/
void OutPutMatrix（int my_rankint group_sizeint epint mynum）
{
	int ij;

	if（my_rank != 0）
	{
		for（i=0;i		{
			printf（“Processor %d:\t“my_rank）;
			for（j=0;j			{
				if（W（ij） > 1000000） printf（“M\t“）;
				else printf（“%d\t“（int）W（ij））;
			}
			printf（“\n“）;
		}
	}
}


/**输出结果**/
void OutPutResult（int my_rankint group_sizeint epint mynum）
{
	int ij;
	if（my_rank != 0）
	{
		for（i=0;i		{
			printf（“node  %d:\t%d\n“（my_rank-1）*ep+i（int）dist[i]）;
		}
	}
}

/**算法主循环**/
void FindMi

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        352  2009-08-13 23:51  并行dijkstra最短路径算法\readme.txt

     文件       7775  2009-08-13 15:10  并行dijkstra最短路径算法\shortest.c

     文件       8074  2009-08-13 23:05  并行dijkstra最短路径算法\ShortestEnhance.c

     文件      40448  2009-08-13 23:17  并行dijkstra最短路径算法\并行dijkstra最短路径算法.doc

     文件      30104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\1.txt

     文件      31650  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\1result.txt

     文件      60104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\2.txt

     文件      31607  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\2result.txt

     文件      90104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\3.txt

     文件      31583  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\3result.txt

     文件     120104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\4.txt

     文件      31587  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\4result.txt

     文件     150104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\5.txt

     文件      31593  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\5result.txt

     文件     180104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\6.txt

     文件      31561  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\6result.txt

     文件     210104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\7.txt

     文件      31559  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\7result.txt

     文件     240104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\8.txt

     文件      31586  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\8result.txt

     文件     270104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\9.txt

     文件      31613  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\9result.txt

     文件     300104  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\a.txt

     文件      31598  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\aresult.txt

     文件        371  2003-07-14 02:22  并行dijkstra最短路径算法\测试数据\readme.txt

     目录          0  2009-08-21 14:05  并行dijkstra最短路径算法\测试数据

     目录          0  2010-08-19 10:25  并行dijkstra最短路径算法

----------- ---------  ---------- -----  ----

              2023997                    27



............此处省略0个文件信息