利用 迪积斯特拉 算法求 " 有向图 " 中某点到其余各点的最短路径
并输出从该点到各点的详细路径,以及总权值。这个程序上学期就写了
今天偶然发现有两个错误，查了我将近两个小时，一个是不可达点的
输出不明显，最大的错误是重复释放了一个指针，我以为是算法错了
从头查到尾，增加了详细的注释，这或者会影响阅读代码，的确，过
多的注释会让代码阅读者不能真正理解代码，当然这也要代码可读性
高。是的代码应该强调，可读性，简洁性，其次才是高效性。
输入: 首先输入图的顶点数 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 : 7
From 3 to 5: 3-5 total value is : 5
From 3 to 6: 3-6 total value is : 1
From 3 to 7: 3-6-7 total value is : 2
Press 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;
}
评论