利用 迪积斯特拉 算法求 " 有向图 " 中某点到其余各点的最短路径 并输出从该点到各点的详细路径,以及总权值。这个程序上学期就写了今天偶然发现有两个错误，查了我将近两个小时，一个是不可达点的输出不明显，最大的错误是重复释放了一个指针，我以为是算法错了从头查到尾，增加了详细的注释，这或者会影响阅读代码，的确，过多的注释会让代码阅读者不能真正理解代码，当然这也要代码可读性高。是的代码应该强调，可读性，简洁性，其次才是高效性。 输入: 首先输入图的顶点数 n 边数 m 接着下一行输入源点 sourcePoint 然后输入每一条边的数据包括 起点s，终点e，权值v 包括起点，终点，权值 (顶点从 1 开始编号) 输出: 输出到各点的详细路径以及权值 事例: (建议用管道测试) 输入文件 data.txt 内容如下： 7 12 3 1 2 3 2 6 7 6 5 9 5 4 2 1 4 3 1 3 6 3 6 1 3 5 5 6 7 1 1 7 2 4 7 10 5 7 5 输出： The shortest path as followed :From 3 can't to 1 !From 3 can't to 2 !From 3 to 4: 3-5-4 total value is : 7From 3 to 5: 3-5 total value is : 5From 3 to 6: 3-6 total value is : 1From 3 to 7: 3-6-7 total value is : 2Press any key to continue 编译环境：VC ++ 6.0 Author ： 江南孤峰 Time ：2007--3--21 #include <stdio.h>#include <process.h>#include <stdlib.h>#include <limits.h>#include <malloc.h>#include <string.h> typedef struct Side{// 路径中的节点 int point; // 节点编号 struct Side *next;}DefSide; typedef struct Result{// 最短路径属性 int flag; // 标记 int start; // 路径的起始点，（除源点） int totalVaule; // 整条路径的总权值 DefSide *thead; // 路径经过的各个节点}DefResult; int main(){ int sourcePoint; int nNode,nSide,s,e,v,i,j; int *meter,nflag; DefResult *presult; DefSide *temp,*temp2; scanf("%d %d",&nNode,&nSide); scanf("%d",&sourcePoint); // 用链表存储最短路径，共有(nNode-1)条路径,因为下标从1开始 presult = (DefResult *)malloc(sizeof(DefResult) * nNode); // 分配对应大小的矩阵,为便于理解，行列下标都从1开始 meter=(int*)malloc(sizeof(int)*(nNode+1)*(nNode+1)); memset(meter,0,sizeof(int)*(nNode+1)*(nNode+1)); for(i = 1; i <= nSide; i ++){ scanf("%d %d %d",&s,&e,&v); *(meter + s * nNode + e) = v; } // 初始化从源点到各点的最短路径，并求出与源点直接连接权值最小的点 for(i = 1,v = INT_MAX; i <= nNode; i ++){ // 标记从源点到对应点的最短路径未求出 presult[i].flag = 0; // 路径初始化为空 presult[i].thead = NULL; // 从源点到该点没有直接连接 if( !*(meter + sourcePoint*nNode + i) ){ // 路径没有起始点（除源点），设值为 -1 presult[i].start = -1; // 路径长度初始化为最大: INT_MAX presult[i].totalVaule = INT_MAX; continue; } // 从源点到该点有直接连接，路径长度初始化为源点到该点的权值 presult[i].totalVaule = *(meter + sourcePoint*nNode + i); // 路径从该点开始（除源点） presult[i].start = i; // 求出与源点直接连接权值最小的点，权值存于 v 中，点编号存于 s 中 if(v > *(meter + sourcePoint*nNode + i)){ v = *(meter + sourcePoint*nNode + i); s = i; } } // 标记该点不必考虑了，值为 0 *(meter + sourcePoint*nNode + s) = 0; // 标记从源点到该点的最短路径已经找到 presult[s].flag = 1; //源点到源点也标记完成 presult[sourcePoint].flag = 1; // 从源点到 n 个顶点的最短路径是否求完，有两个点已经完成即 // 源点和与源点直接邻接并且权值最小的点，nflag 初始化为 2 for(nflag = 2; nflag <= nNode; nflag ++){ // s是目前源点到其它点最短路径的结束点 v = presult[s].totalVaule; // 扫描从 s 出发到其他各点的权值，以决定是否更新邻接表和路径链表 for(i = 1; i <= nNode; i ++){ if(*(meter + s*nNode + i) && (v + *(meter + s*nNode + i) < presult[i].totalVaule)){ presult[i].totalVaule = v + *(meter + s*nNode + i); presult[i].start = presult[s].start; // 更新从源点到点 i 的路径 while(presult[i].thead){ temp = presult[i].thead; presult[i].thead = temp -> next; free(temp); } if(presult[s].thead){ temp2 = presult[i].thead = (DefSide*)malloc(sizeof(DefSide)); presult[i].thead->point= presult[s].thead->point; temp = presult[s].thead; while(temp->next){ temp = temp -> next; temp2 = temp2->next = (DefSide*)malloc(sizeof(DefSide)); temp2->point = temp->point; } temp2 = temp2->next = (DefSide*)malloc(sizeof(DefSide)); temp2->point = i; temp2->next = NULL; } else{ presult[i].thead = (DefSide*)malloc(sizeof(DefSide)); presult[i].thead->point = i; presult[i].thead->next = NULL; } } } // 筛选目前结果中的最短路径 for(j = 1,v = INT_MAX; j <= nNode; j ++){ if(!presult[j].flag && presult[j].totalVaule && presult[j].totalVaule < v){ v = presult[j].totalVaule; s = j; } } // 标记从源点到 s 点的最短路径已经找到 presult[s].flag = 1; *(meter + sourcePoint*nNode + s) = 0; } printf("The shortest path as followed :\n"); for(i = 1; i <= nNode; i ++){ if(i == sourcePoint) continue; if(presult[i].start == -1){ printf("From %d can't to %d !\n",sourcePoint,i); continue; } printf("From %d to %d: %d-%d",sourcePoint,i,sourcePoint,presult[i].start); temp = presult[i].thead; while(temp){ printf("-%d",temp -> point); temp2 = temp; temp = temp -> next; free(temp2); } printf(" total value is : %d\n",presult[i].totalVaule); } free(meter); return EXIT_SUCCESS;}
评论