資源簡介
并行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個文件信息
- 上一篇:小功率調頻發射機設計報告
- 下一篇:.net文件的分割與合并處理
評論
共有 條評論