看数据结构写代码(47)迪杰斯特拉最短路径算法
这个算法的 思想 根 求 最小生成树算法 普里姆(Prim)算法 极其相似。迪杰斯算法 是求 一个顶点 到其他 顶点的 最短路径算法。
下面 上代码:(用的是 邻接矩阵 表示法)
//迪杰斯特拉 最短路径。 //从 vex顶点 到其他 顶点的 最短路径 void shortestPath_Dij(MGraph g,char vex){ int loc = graphLocation(g,vex); int minArray[MAX_VERTEX_NUM]={0};//最小路径值 bool final[MAX_VERTEX_NUM] = {false};//是否已经完成最小路径 //初始化vex 到vex 的 数据 minArray[loc] = 0; final[loc] = true; int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//路径数组,每一行 存放 vex 到这一行的 最短路径 int pathLenArray[MAX_VERTEX_NUM] = {0};//存放每行路径数组的个数. for (int i = 0; i < g.vexNum; i++){ minArray[i] = g.arcs[loc][i].adj; if (minArray[i] < INFINITY){//vex 指向 i path[i][0] = i; pathLenArray[i] = 1; } } for (int i = 1; i < g.vexNum; i++)//g.verNum -1 个路径 { int min = INFINITY;//最小路径值 int minIndex = -1;//当前最小路径索引 int notFind = -1; for (int i = 0; i < g.vexNum; i++){//在 minArray 里 寻找 值最小的(不包括已完成的) if (final[i] == false){ if (minArray[i] < min){ min = minArray[i]; minIndex = i; } else { notFind = i; } } else if(final[i] == false){//没找到. notFind = i; } } if(minIndex == -1){//无路径时特殊处理 minIndex = notFind; } final[minIndex] = true;//设置 已找到 最小路径 //打印最小路径,以及 最小路径值 if (minIndex != notFind){ printf("%c 到 %c ,最小路径值为:%d,路径为:%c",vex,g.vexs[minIndex],min,vex); } else{ printf("%c 到 %c 不可达",vex,g.vexs[minIndex],min,vex); } int minLen = pathLenArray[minIndex]; for (int i = 0; i < minLen; i++){ printf("→ %c",g.vexs[path[minIndex][i]]); } printf("\n"); for (int i = 0; i < g.vexNum; i++){//重新 计算 最小路径 数组 if (final[i] == false){ int newMin = min + g.arcs[minIndex][i].adj; if (newMin < minArray[i]){ minArray[i] = newMin; //重新设置路径 int j; for (j = 0; j < pathLenArray[minIndex]; j++){ path[i][j] = path[minIndex][j]; } path[i][j] = i; pathLenArray[i] = j+1;//设置数组长度. } } } } }
在写 这段代码的时候遇到了两个问题:
1.数值 溢出,书中 用的 INT_MAX ,来表示 顶点之间 不可达的 关系。
当重新计算 最小路径数组的时候 int newMin = min + g.arcs[minIndex][i].adj; 如果 遇到了 INT_MAX,那么代码 逻辑 混乱。
所以 我把 INT_MAX 变成 短整型
#define INFINITY SHRT_MAX
2. 书中的 代码 当 没有 找到 最小值时,然后 访问 final数组 会 堆栈 溢出。加了一个特殊处理。
if(minIndex == -1){//无路径时特殊处理 minIndex = notFind; }
完整源代码网盘地址:点击打开链接
运行截图:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。