最短路径算法源程序代码(共21页)

1、精选优质文档-倾情为你奉上#include <stdio.h>#include <conio.h>#include <string.h>#define JiedianNum 6 /最大结点数#define NameLenght 3 /节点名字长度#define Infinity 10000 /若节点间没有路径距离设定为Infinitychar *JiedianNameFile="jiedianname.txt" /图的顶点-节点名char *JiedianPathFile="jiedianpath.txt" /边-节点

2、间的连接关系char *MinPathDataFile="minpath.txt" /最短路径数据/*/* 从文件中读入结点数据 */* 函数参数： */* char jiedian:存放节点名的数组 */* int *NodNum:指针变量，指向存放节点个数的变量 */* 输入数据：文本数据文件：JiedianNameFile */* 文件数据格式： */* <节点个数> */* <节点名> */* 输出数据：指从该函数中带回到调用函数的数据，包括： */* jiedian-节点名称 */* NodeNum-节点名的个数 */* 返回值：数据读入是

3、否成功的标志 */ /* 0-失败 1-成功 */*/int InputJiedianNode(char jiedianNameLenght,int *NodeNum ) int i,n; FILE *fp; if(!(fp=fopen(JiedianNameFile,"r") printf("节点数据文件不存在n"); getch(); return(0); fscanf(fp,"%d",&n); if(!n) printf("文件中无节点数据!n"); getch(); return(0); for(i

4、=0;i<n;i+) fscanf(fp,"%s",jiediani); fclose(fp); *NodeNum=n; return(1); /*/* 从文件中读入最短路径数据 */* 函数参数： */* int dist:节点间最短路径的值 */* int Path:节点间最短路径结点数据 */* int *NodNum:指针变量，表示读入数据的多少 */* 输入数据：数据文件：MinPathDataFile */* 文件数据格式：二进制数据，数据存放顺序： */* <节点个数n><n*n个最短路径值><n*n个结点值> */*

5、 输出数据：指从该函数中带回到调用函数的数据，包括： */* jiedian */* Path */* NodeNum */* 返回值：数据读入是否成功的标志 */* 0-失败 1-成功 */*/int InputMinPath(int distJiedianNum,int PathJiedianNum,int *NodeNum) int n; FILE *fp; if(!(fp=fopen(MinPathDataFile,"rb") printf("最小路径数据文件不存在!n"); getch(); return(0); fread(&n,si

6、zeof(int),1,fp); fread(dist,sizeof(int),n*n,fp); fread(Path,sizeof(int),n*n,fp); fclose(fp); *NodeNum=n; return(1); /*/* 查找节点名 */* 函数参数： */* char str:存放节点名的数组 */* int n：str中数据的行数，即节点名的个数 */* char *p:指针变量，表示需要查找的节点名 */* 输入数据：全部函数参数均为输入数据 */* 输出数据：返回值作为函数的输出数据 */* 查找成功：被查找的节点名在数组str中的序号 */* 查找失败：1，表示被

7、查找的节点名未出现在数组中 */*/int search(char strNameLenght,int n,char *p) int i=0; while(i<n) if(!strcmp(stri,p) return(i); i+; return(-1); /*/* 计算节点间最短路径 */* 函数参数：<无> */* 输入数据：文本数据文件：JiedianNameFile */* 文件数据格式： */* <节点个数> */* <节点名> */* 文本数据文件：JiedianPathFile */* 文件数据格式： */* <边数> */*

8、 <结点名><节点名><边值> */* 输出数据：数据文件：MinPathDataFile */* 文件数据格式：二进制数据，数据存放顺序： */* <结点个数n><n*n个最短路径值><n*n个结点值> */* 返回值：<无> */* 说明：文本数据文件中数据间用空格或换行符格开 */*/void shorttestpath() int i,j,k,NodeNum,EgeNum,val; int arcJiedianNumJiedianNum; /权值矩阵 char jiedianJiedianNumName

9、Lenght; /结点 int distJiedianNumJiedianNum; /最短路径长度矩阵 int PathJiedianNumJiedianNum; /最短路径矩阵 char jiedian1NameLenght,jiedian2NameLenght; FILE *fp; /*-*/ /* 算法步骤： */ /* 1、读入结点数据 */ /* 2、邻接矩阵初始化：所有元素赋Infinity， */ /* 对角线元素赋0 */ /* 3、读入结点间边的数据，转换为邻接矩阵的数据 */ /* 4、路径矩阵初始化，若arcij<Infinity， */ /* 则： atij=i

10、否则：Pathij=-1 */ /* 5、计算最短路径 */ /* 6、保存最小路径数据 */ /*-*/ /-初始化邻接矩阵- if(!InputJiedianNode(jiedian,&NodeNum) return; else for(i=0;i<NodeNum;i+) for(j=0;j<NodeNum;j+) if(i=j) arcij=0; else arcij=Infinity; printf("%sn",jiediani); /-读入结点间边的数据- if(!(fp=fopen(JiedianPathFile,"r")

11、 printf("结点间边的数据文件不存在!n"); getch(); return; fscanf(fp,"%d",&EgeNum); if(!EgeNum) printf("文件中无结点间边的数据!n"); getch(); return; for(k=0;k<EgeNum;k+) fscanf(fp,"%s",jiedian1); fscanf(fp,"%s",jiedian2); fscanf(fp,"%d",&val); i=search(ji

12、edian,NodeNum,jiedian1); j=search(jiedian,NodeNum,jiedian2); arcij=arcji=val; fclose(fp);/-路径矩阵初始化- for(i=0;i<NodeNum;i+) for(j=0;j<NodeNum;j+) if(arcij<Infinity)&&(i!=j) Pathij=i; else Pathij=-1; /初始化 最短路径长度矩阵 dist for(i=0;i<NodeNum;i+) for(j=0;j<NodeNum;j+) distij=arcij; /弗罗

13、伊德算法 for(k=0;k<NodeNum;k+) for(i=0;i<NodeNum;i+) for(j=0;j<NodeNum;j+) if(distik+distkj<distij) distij=distik+distkj; Pathij=Pathkj; /-保存城市间最短路径的信息- if(!(fp=fopen(MinPathDataFile,"wb") printf("打不开文件 %s !n",MinPathDataFile); getch(); return; fwrite(&NodeNum,sizeof(

14、int),1,fp); fwrite(dist,sizeof(int),NodeNum*NodeNum,fp); fwrite(Path,sizeof(int),NodeNum*NodeNum,fp); fclose(fp); return;/*/* 求一个节点到其它节点的最短路径 */* 函数参数：<无> */* 输入数据：文本数据文件：JiedianNameFile */* 数据文件：MinPathDataFile */* 指定节点名,从键盘输入 */* 输出数据： */* 指定节点到其它所有节点的最短路径值和路径 */* (屏幕显式) */* 返回值：<无> */

15、*/void One_To_Other_Path() int i,j,k,NodeNum,StartNode; char jiedianJiedianNumNameLenght; /结点 int distJiedianNumJiedianNum; /最短路径长度矩阵 int PathJiedianNumJiedianNum; /最短路径矩阵 int top,PathStackJiedianNum; char jiedian1NameLenght; FILE *fp;/*-*/ /* 算法步骤： */ /* 1、输入结点数据 */ /* 2、输入最小路径数据 */ /* 3、输入起点节点名称，并

16、确定其正确性 */ /* 方法：调用查找函数，若返回值>=0则正确 */ /* 4、依次求起点节点到其它节点的最短路径 */ /* 方法：根据两节点的序号i,j在dist数组中获得 */ /* 最短路径值。根据Path数组中结点间路径 */ /* 数据的关系求的其结点序列并放入栈中， */ /* 然后依次输出栈数据。 */ /*-*/ /从文件中读入结点数据 if(!InputJiedianNode(jiedian,&NodeNum) printf("读取节点文件失败 %s !n",JiedianNameFile); getch(); return; /从文件

17、中读入最小路径数据 if(!InputMinPath(dist,Path,&NodeNum) printf("读取最短路径文件失败 %s!n",MinPathDataFile); getch(); return; /输入起点节点名 printf("请输入节点名称: "); scanf("%s",&jiedian1); k=search(jiedian,NodeNum,jiedian1); if(k<0) printf("错误的节点名称 %s !n",jiedian1); getch(); re

18、turn; /获得路径结点关系，并依次入栈 for(i=0;i<NodeNum;i+) j=i; top=StartNode=0; if(i=k) continue; printf("起始节点和终止节点: %s=>%sn",jiediank,jiediani); printf("最短路径: %d kmn",distki); PathStacktop+=j; while(Pathkj!=k) PathStacktop+=Pathkj; j=Pathkj; /依次输出最小路径上的结点 printf("最短路经: n%s",ji

19、ediank); while(top) printf("=>%s",jiedianPathStack-top); getch(); printf("nn"); /*/* 求一个节点到另一个节点的最短路径 */* 函数参数：<无> */* 输入数据：文本数据文件：JiedianNameFile */* 数据文件：MinPathDataFile */* 起点节点名,终点节点名，从键盘输入 */* 输出数据： */* 起点节点到终点节点的最短路径值和路径 */* (屏幕显式) */* 返回值：<无> */*/void One_To

20、_One_Path() int i,j,k,NodeNum,StartNode,EndNode; char jiedianJiedianNumNameLenght; /结点 int distJiedianNumJiedianNum; /最短路径长度矩阵 int PathJiedianNumJiedianNum; /最短路径矩阵 int top,PathStackJiedianNum; char jiedian1NameLenght,jiedian2NameLenght; FILE *fp; /*-*/ /* 算法步骤： */ /* 1、输入结点数据 */ /* 2、输入最小路径数据 */ /*

21、 3、输入起点节点和终点节点名称，并确定其正确性 */ /* 方法：调用查找函数，若返回值>=0则正确 */ /* 4、求起点节点到终点节点的最短路径 */ /* 方法：根据两节点的序号i,j在dist数组中获得 */ /* 最短路径值。根据Path数组中结点间路径 */ /* 数据的关系求的其结点序列并放入栈中， */ /* 然后依次输出栈数据。 */ /*-*/ /从文件中读入结点数据 if(!InputJiedianNode(jiedian,&NodeNum) printf("读取节点文件失败 %s !n",JiedianNameFile); getch

22、(); return; /从文件中读入最小路径数据 if(!InputMinPath(dist,Path,&NodeNum) printf("读取最短路径文件失败%s !n",MinPathDataFile); getch(); return; /用户输入起点节点和终点节点 printf("请输入起始节点名称: "); scanf("%s",jiedian1); printf("请输入终止节点名称: "); scanf("%s",jiedian2); /调用查找函数， StartNode

23、=search(jiedian,NodeNum,jiedian1); EndNode=search(jiedian,NodeNum,jiedian2); if(StartNode<0|EndNode<0) / 检测节点名正确性 printf("错误的节点名称!n"); getch(); return; /获得结点关系，并依次进栈，输出之 printf("距离为 %s=>%s: %d kmn",jiedian1,jiedian2,distStartNodeEndNode); i=StartNode; j=EndNode; top=0; PathStacktop+=j; /终点节点入栈 while(Pathij!=i) PathStacktop+=Pathij; /最短路径上其它结点入栈