第k短路径 数据结构课设 A*算法Yen算法

基本概念

首先介绍一下偏离的概念。

我们考虑武汉到北京。
1，首先最短路径是武汉->郑州->石家庄->北京。
2，那么举例另一条路径武汉->郑州->太原->石家庄->北京。
3，那么第二条路径相对于第一条路径的偏离节点就是郑州，通俗讲就是分叉点。
4.偏离边就是郑州->太原。
我们不需要知道为啥他是偏离点和偏离边，只需要知道怎么做就好了。

算法核心

求第k+1短路径时
偏离点：第k短路径上除了终点的所有路径点。选取一个当前偏离点u。
不能用的点：第k短路径上当前偏离点的前面所有路径点。
不能用的边：第1短，第2短……前k短路径中所有以当前偏离点为起点的边。(目的在于得到不同于已经求出的最短路径的路径）
对u调用dijsktra算法求u到终点的最短路径和距离，那么这一条候选路径就是就是u之前的路径点拼接上dij求出来的路径，距离长度就是他们的和。
每一个偏离点求一个候选路径，最后求所有路径的最小值，输出第k短路径。

具体操作例子

1，首先调用dijsktra算法求出武汉到北京的一条最短路径，很清楚了。
武汉->郑州->石家庄->北京。
2，以这条最短路径为基础，我们去求次短路径。
（1），把最短路径的第一个点看作偏离点。（武汉）
（2），得到不能用的点（此时武汉前面没有点）和不能用的边（武汉->郑州）。
（3），调用dijsktra得到武汉到北京的最短距离，（注意此时的区别就在不能用的点和不能用的边）
（4）候选路径：武汉 合肥 济南 石家庄 北京 1388
重复1234步骤
（1）把最短路径的第二个点看作偏离点。（郑州）
（2），得到不能用的点（武汉）和不能用的边（郑州->石家庄）。
（3），调用dijsktra得到郑州到北京的最短距离。
（4）候选路径：武汉 郑州 太原 石家庄 北京 1263
（1）把最短路径的第三个点看作偏离点。（石家庄）
（2），得到不能用的点（武汉，郑州）和不能用的边（石家庄->北京）。
（3），调用dijsktra得到石家庄到北京的最短距离。
（4）候选路径：武汉 郑州 石家庄 天津 北京 1206
偏离点遍历完毕，求出第二短路径 （武汉 郑州 石家庄 天津 北京 1206）
第k短重复上面操作。

emmm我发现这里我讲的很烂，但是代码很详细有注释，看代码就能理解每一步了。

代码

结构体

struct  allpathdist
{int dis;//距离string arr[15];//路径allpathdist(int a = 0):dis(a){for (int i = 0; i < 15; i++) arr[i] = " ";}
};allpathdist *houxuanpath = new allpathdist[1000];//候选路径
allpathdist *finalpath = new allpathdist[1000];//最短路径

A*

void graph::Astar(graph& G, int v, int p, int k)
{int unavilablenode[1000];//不能走的点集合notedge unavilableedge[1000];//不能走的边集合G.singledij(G, v, p, unavilablenode, unavilableedge);//得到第一条最短路径finalpath[0] = houxuanpath[0];//我设置的最短路径集合和候选路径集合G.Btime++;//最短路径的条数cout << "第1条最短路径：" << endl;printpath(0);//输出clearpath(); //从候选路径集合中删除最短路径G.Atime--;//候选路径条数int kk = 1;//要求的第kk+1条最短路径while (kk < k){int num = 0;while (finalpath[kk - 1].arr[num] != " ") num++;//k-1短路径中节点个数//遍历每一个偏离节点for (int i = 0; i < num-1; i++){int pianli = getloc(finalpath[kk - 1].arr[i]);//偏离点的下标int w = 0;//起点到偏离点的距离for (int j = 0; j < i; j++) w += earry[getloc(finalpath[kk - 1].arr[j])][getloc(finalpath[kk - 1].arr[j + 1])];//1，得到不能走的节点和边，for (int j = 0; j < 1000; j++) unavilablenode[j] = unavilableedge[j].begin = unavilableedge[j].end = -1;//数组初始化for (int j = 0; j < i; j++)//不能走的节点集合{unavilablenode[j] = getloc(finalpath[kk - 1].arr[j]);}int kkk = kk;int edgenum = 0;while (kkk > 0)//不能走的边集合{num = 0;while (finalpath[kkk - 1].arr[num] != " ") num++;//k-1短路径中节点个数for (int j = 0; j < num-1; j++){if (getloc(finalpath[kkk - 1].arr[j]) == pianli){unavilableedge[edgenum].begin = pianli, unavilableedge[edgenum].end = getloc(finalpath[kkk - 1].arr[j + 1]);edgenum++;break;}}kkk--;}//2,//偏离点到终点的最短路径G.singledij(G, pianli, p, unavilablenode, unavilableedge);int numpianli=0;//偏离点到终点路径的节点数目houxuanpath[G.Atime - 1].dis += w;while(houxuanpath[G.Atime - 1].arr[numpianli] != " ") numpianli++;for (int j = numpianli-1; j > -1; j--) houxuanpath[G.Atime - 1].arr[j + i] = houxuanpath[G.Atime - 1].arr[j];//数组后移for (int j = 0; j < i; j++) houxuanpath[G.Atime - 1].arr[j] = finalpath[kk - 1].arr[j];//讲偏离点前的路径点拼接到候选路径上judge(G);//判断当前路径在候选路径中是否存在如果已有相同路径就删除}sortpath(houxuanpath, houxuanpath + G.Atime, cmp);//对候选路径进行排序finalpath[kk] = houxuanpath[0];//最短的候选路径进入最短路径集合G.Btime++;clearpath();G.Atime--;cout << "第" << kk+1 << "短路径：" << endl;printpath(kk);kk++;}
}

Dijsktra

void graph::singledij(graph& G, int v, int p, int unavilablenode[], notedge unavilableedge[])
{bool* s = new bool[numv];int* dist = new int[numv];int* path = new int[numv];for (int i = 0; i < numv; i++)//辅助数组的初始化{if (i == v) dist[i] = 0;else if (neigh[v][i] == 1) dist[i] = earry[v][i];else dist[i] = 32767;s[i] = false;if (i != v && dist[i] < 32767) path[i] = v;else path[i] = -1;}s[v] = true;dist[v] = 0;//不能走的点int time = 0;while (unavilablenode[time] > -1 && unavilablenode[time] < 34){s[unavilablenode[time]] = true;//直接进入s集合time++;}//不能走的边time = 0;while (unavilableedge[time].begin != -1 && unavilableedge[time].end != -1){dist[unavilableedge[time].end] = 32767;//当前dist置无穷表不可达path[unavilableedge[time].end] = -1;time++;}//下面就是dij的常规了for (int i = 0; i < numv - 2; i++){int min = 32767;int u = v;for (int j = 0; j < numv; j++){if (s[j] == false && dist[j] < min){u = j;min = dist[j];}}if (u == v) break;//从原点出发 无法与其他节点联通 不继续进行（注意再注意：这里有一个很大的坑，我改了很久才发现，举个例子，现在dij求得是石家庄到北京的最短路径，而我们不能用的边是石家庄到北京和石家庄到天津，那么虽然dist[北京]dist[天津]都是无穷，因为北京和天津通过别的任何节点都不能加入，所以最后会以石家庄为原点更新dist，那么我们设置的不能走的边就没用了。解决办法就是找不到任何其他需要加的节点时，证明不连通就不更新dist直接break掉就ok了。s[u] = true;for (int k = 0; k < numv; k++)//更新dist[]和path[]{if (neigh[u][k] == 1){int w = earry[u][k];if (s[k] == false && w < 32767 && dist[u] + w < dist[k]){dist[k] = dist[u] + w;path[k] = u;}}}}if (dist[p] == 32767) return;//偏离点到终点没有最短路径else//加入候选数组{houxuanpath[G.Atime].dis = dist[p];int kk = 0;int pp = p;while (path[pp] != -1){pp = path[pp];kk++;}for (kk; kk > -1; kk--){houxuanpath[G.Atime].arr[kk] = vlist[p].data;p = path[p];}}G.Atime++;
}

反思

自己写算法写了好久，又要调试bug，最终测试结果发现少了几条路径，原来是Yen适用无环图。
问题在于武汉到北京，武汉到天津的路都被当作不可用的边后，后面任何到达石家庄的路径都走不进不去，我一开始想法是，那不如每次只算第k-1条最短路径的偏离边，就算有重复得到的那我比对最短路径集合全删去就好了，但结果又会因为不能用的边的减少，一些其他的路径会消失。
想想也是，存在几十年的算法了，适用无环图，怎么可能让我两下解决问题呢，真是裂开。
传送门