现在来了解 A * 算法是什么
现在来解决 A * 求 K 短路问题
在一个有权图中, 从起点到终点最短的路径成为最短路, 第 2 短的路成为次短路, 第 3 短的路成为第 3 短路, 依此类推, 第 k 短的路成为第 k 短路. 那么, 第 k 短路怎么求呢?
对于第 k 短路, 可以想到的一个比较朴素的算法就是广度优先搜索, 使用优先队列从源点 s 进行广搜, 当第 k 次搜索到终点 t 时, 所的长度即所求但是这种方法在运行过程中会产生特别多的状态, 当图比较简单, k 比较小时, 可以一试, 但是当 k 较大或者图中点数较多时, 会面临爆栈的危险. 目前使用比较多的算法是单源最短路配合 A*.A * 是搜索中比较高级的方式, A * 算法结合了启发式方法 (这种方法通过充分利用图给出的信息来动态的作出决定而使搜索次数大大降低) 和形式化方法 (这种方法不利用图给出的信息, 而仅通过数学的形式分析, 如 Dijkstra 算法). 它通过一个估价函数 f(h) 来估计图中的当前点 p 到终点的距离, 并由此决定它的搜索方向, 当这条路径失败时, 它会尝试其他路径. 对于 A*, 估价函数 = 当前值 + 当前位置到终点的距离, 即 f(p)=g(p)+h(p), 每次扩展估价函数值最小的一个. 对于第 k 短路算法来说, g(p)为从源点 s 到当前点 p 所走的路径长度, h(p)为从当前点 p 到终点 t 的最短路, 因此 f(p)的意义就是从 s 按照当前路径经过 p 点后到达 t 的总距离. 也就是每次扩展都是有方向的, 这样无论对提高出解的速度还是降低扩展的状态数目都是有好处的. 为了加快计算, h(p)需要在搜索之前进行预处理, 只要将原图的所有边反向, 再从终点 t 做一次单源最短路即可得到 h(p). 单源最短路求法有 Dijkstra,Bellman-Ford,SPFA 等.
具体步奏:
这里我们使用链式前向星来存储如图, 由于需要预处理所有点到终点的最短路, 就需要将图 G 中所有边反向得到图 G', 再从终点 t 做一次单源最短路, 所以实际上就是两张图.
(1)将有向图的所有边反向 (无向图可以省略此步), 以原图终点 t 为源点做一次单源最短路, 结果记入数组 dis[i] 中, dis[i]即为原图中点 i 到点 t 的最短距离. 这里的 dis[i]即上述的 h(p);
(2)新建一个优先队列, 将源点 s 加入到队列中;
(3)从优先队列中弹出 f(p)最小的点 p(这里如果存在 f(p)相等的点, 则弹出 g(p)最小的点), 如果点 p 就是终点 t, 则计算 t 出队列的次数, 如果当前为 t 的第 k 次出队, 则当前路径长度就是 s 到 t 的第 k 短路, 算法结束; 否则遍历与 p 相连的所有的边, 将扩展出的到 p 的邻接点信息加入到优先队列.
值得注意的是, 当 s==t 时需要计算 (k+1) 短路, 因为 s 到 t 这条距离为 0 的路不能算在这 k 短路中, 这时只需将 k 自增 1 后再求第 k 短路即可.
现在来实战下:
题意 : 给出一个有向图, 求起点 s 到终点 t 的第 k 短路, 不存在则输出 -1
- #include<stdio.h>
- #include<string.h>
- #include<queue>
- #include<algorithm>
- using namespace std;
- const int INF = 0x3f3f3f3f;
- const int maxn = 1024;
- const int maxm = 100008;
- struct EDGE{ int v, nxt, w; };
- struct NODE{
- int pos, Cost, F;
- bool operator <(const NODE & rhs) const {// 重载的时候注意符号
- if(this->F == rhs.F) return this->Cost> rhs.Cost;
- return this->F> rhs.F;
- };
- };
- EDGE Edge[maxm];
- EDGE REdge[maxm];
- int Head[maxn], RHead[maxn];
- int cnt, Rcnt;
- int N;
- void init()
- {
- memset(Head, -1, sizeof(Head));
- memset(RHead, -1, sizeof(RHead));
- cnt = Rcnt = 0;
- }
- void AddEdge(int from, int to, int weight)
- {
- Edge[cnt].w = weight;
- Edge[cnt].v = to;
- Edge[cnt].nxt = Head[from];
- Head[from] = cnt++;
- }
- void AddREdge(int from, int to, int weight)
- {
- REdge[Rcnt].w = weight;
- REdge[Rcnt].v = to;
- REdge[Rcnt].nxt = RHead[from];
- RHead[from] = Rcnt++;
- }
- int vis[maxn];
- int H[maxn];
- void SPFA(int st)
- {
- queue<int> que;
- memset(H, INF, sizeof(H));
- memset(vis, 0, sizeof(vis));
- H[st] = 0;
- que.push(st);
- while(!que.empty()){
- int cur = que.front(); que.pop();
- vis[cur] = 0;
- for(int i=RHead[cur]; i!=-1; i=REdge[i].nxt) {
- int v = REdge[i].v;
- if(H[v]> H[cur] + REdge[i].w) {
- H[v] = H[cur] + REdge[i].w;
- if(!vis[v]) {
- vis[v] = 1;
- que.push(v);
- }
- }
- }
- }
- }
- int A_Star(int s, int t, int k)
- {
- if(s == t) k++;
- if(H[s]==INF) return -1;
- priority_queue<NODE> que;
- NODE cur, into;
- cur.pos = s;
- cur.Cost = 0;
- cur.F = H[s];
- que.push(cur);
- int CNT = 0;
- while(!que.empty()){
- cur = que.top();
- que.pop();
- if(cur.pos == t) CNT++;
- if(CNT == k) return cur.Cost;
- for(int i=Head[cur.pos]; i!=-1; i=Edge[i].nxt){
- into.Cost = cur.Cost+Edge[i].w;
- into.F = cur.Cost+Edge[i].w+H[Edge[i].v];
- into.pos = Edge[i].v;
- que.push(into);
- }
- }return -1;
- }
- int main(void)
- {
- int M, K, S, des;
- while(~scanf("%d %d", &N, &M)){
- init();
- int from, to, weight;
- while(M--){
- scanf("%d %d %d",&from, &to, &weight);
- AddEdge(from, to, weight);
- AddREdge(to, from, weight);// 建反向边
- }
- scanf("%d %d %d", &S, &des, &K);
- SPFA(des);// 求其他点到终点的最短路, 作为 H 值
- printf("%d\n", A_Star(S,des,K));
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2763047.html