/**輸入鄰接矩陣和源頂點，求最短路徑。輸入鄰接矩陣中，位置（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??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個文件信息