A* 算法求第K短路径长度

今天药忘吃喽~ 2021-09-21 13:10 178阅读 0赞

### 文章目录 ###

*  A\* 算法求第K短路径
 *   *  简介：
     *  复杂度分析：
     *  例子：

# A\* 算法求第K短路径 #

## 简介： ##

`A*`是一种搜索算法，一般基于一个估价函数f(x) = g(x) + h(x)，通过这个函数来进行有方向的搜索以提高搜索的效率。其中g(x)指从初始状态到当前状态的花费，h(x)为当前状态到终状态的花费的估计值，以两者之和来估计起始状态到终状态的总花费f(x)。在A\*算法中，通过优先搜索最符合要求的f（x）表示的状态以提升搜索效率。

在求第k短路的问题中，g(x)指的是由起点到达当前点的路径长度，h(x)指当前点到达终点的最短路,而此时我们需要优先对估价函数值较小的状态进行搜索。故而可以使用优先队列对数据进行处理。

一般对h(x)提前进行预处理，使用Dijkstra/SPFA预先求好最短路。  
由于A\*总能够优先搜索 当前队列中所有结点距离终状态最近的结点，所以每次搜索到终点时都是当前最近的路。当第k次搜索到终点时的路径长度就是k短路的长度了。

## 复杂度分析： ##

优化了的Dijkstra的时间复杂度可以达到`O(|E|log|V|)`。然后在`A*`算法中，我们计算每次从堆中弹出完整路径（从起点出发抵达终点的路径）过程中最多有|V|条路径被弹出（最短路径不含环），且这过程中最多有|E|个结点被加入堆中。故堆中最多含有k|E|条路径，因此总的时间复杂度为`O(k*(|V|+|E|)log(k|E|))+O(|E|log(|V|))=O(k|E|log(k|E|))`

## 例子： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70_pic_center]

求A到E点第2短路径长度

测试数据：第一行3个数，分别为顶点数(n)，边数(m)，K。第二行分别表示起点和终点，最后的m行表示边

> 5 6 2
> 
> 1 5
> 
> 1 2 1
> 
> 1 3 2
> 
> 1 4 3
> 
> 2 5 5
> 
> 3 5 3
> 
> 4 5 6

具体步骤：

这里使用**邻接表**来存储图，需要**预处理所有点到终点的最短路**，由于这里是一个有向图，再输入数据的时候，另外将边反向存在了**temp邻接表**中，用于利用Dijkstra算法求所有点到终点的最短距离，结果存在数组d\[i\]中。

（1）以原图终点ed为源点做一次单源最短路，结果记入数组d\[i\]中，d\[i\]即为原图中点i到终点ed的最短距离。这里的d\[i\]即上述的h(x);

（2）新建一个优先队列，将源点s加入到队列中；

（3）从优先队列中弹出f(v)最小的点v（这里如果存在f(v)相等的点，则弹出g(v)最小的点），如果点v就是终点ed，则计算ed出队列的次数，如果当前为ed点的第k次出队，则当前路径长度就是st到ed的第k短路，算法结束；否则遍历与点v相连的所有的边，将扩展出的到点v的邻接点信息加入到优先队列。

**代码**

#include<iostream>
    #include<queue>
    #include<vector> 
    #include<algorithm> 
    /* 估计函数f(x) = g(x) + h(x) ，g(x)为起点到当前顶点的花费(距离)，h(x)为当前顶点到终点的最短距离，这里h(x)可以通过Dijkstra先求出来 */ 
    using namespace std;
    const int maxn = 1010; //最大节点数 
    const int INF = 0x3ffffff; //表示不可达 
    int n,m,k,cnt=0; //n为顶点数，m为边数 
    struct ptr{ 
    	int now,f,g; //now为当前节点
    	bool operator < (const ptr& a)const { 
    		return (this->f == a.f) ? this->g > a.g : this->f > a.f;
    	} //设置优先级，f小的优先级高，f相同时,g越小优先级越高 
    };
    struct edge{  //定义边 
    	int v,dis; //v为边的目标顶点,dis为边权 
    }Edge;
    vector<edge>Adj[maxn]; //邻接表存储图，Adj[u]中存放从顶点u出发可以到达的所有顶点 
    vector<edge>temp[maxn];//这个邻接表用来求d[i] 
    bool vis[maxn]={ false}; //标记是否访问
    int d[maxn]; //存放所有顶点到终点的最短距离
    int st,ed; // 起点和终点
    
     
    //求其他所有顶点到终点的距离
    void  Dijkstra(int s){  //这里s要传入终点 
    	fill(d,d+maxn,INF);
    	d[s] = 0;
    	for(int i=1; i<=n; i++){ 
    		int u=-1, MIN = INF;
    		for(int j=1; j<=n; j++){ 
    			if(vis[j] == false && d[j] < MIN){ 
    				u = j;
    				MIN = d[j];
    			}
    		}
    		if(u == -1) return; //不连通 
    		vis[u] = true; //标记为以访问
    		for(int j=0; j < temp[u].size(); j++){ 
    			int v = temp[u][j].v;
    			if(vis[v]==false && d[u] + temp[u][j].dis< d[v]){ 
    				//如果v未访问&&以u为中介点可以使d[v]更优
    				d[v] = d[u] + temp[u][j].dis; //优化d[v] 
    			}
    		} 	
    	}			
    } 
    
    //A*算法
    int A_Star(int st, int ed, int k){ 
    	if(st == ed) k++;
    	if(d[st] == INF) return -1;
    	priority_queue<ptr>q;
    	ptr cur{ st,d[st],0}; //起点
    	q.push(cur);
    	while(!q.empty()){ 
    		ptr t = q.top();
    		q.pop();
    		int u = t.now; //当前顶点
    		if(u == ed)cnt++;//若为终点，cnt加1
    		if(cnt == k) return t.g; //返回第K短路径的长度
    		for(int i=0; i<Adj[u].size(); i++){ 
    			//将邻接顶点的信息加入到队列中
    			int path = t.g + Adj[u][i].dis;
    			int next = Adj[u][i].v;
    			q.push(ptr{ next,path+d[next],path});
    		} 	
    	}
    	return -1;	
    } 
     
     
    int main(){ 
    	scanf("%d%d%d",&n,&m,&k); //顶点数，边数，k值
    	scanf("%d%d",&st,&ed); //起点，终点 
    	for(int i=0; i<m; i++) { 
    		int s,v,dis;
    		scanf("%d%d%d",&s,&v,&dis);//起点 
    		Edge.v = v,Edge.dis = dis;
    		Adj[s].push_back(Edge);
    		//反向边初始化
    		Edge.v = s,Edge.dis = dis;
    		temp[v].push_back(Edge); 
    	}
    	Dijkstra(ed);//d[index]为顶点index到终点的最短距离，也等于h(index) 
    	int ans = A_Star(st,ed,k); 
    	printf("%d",ans);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70_pic_center 1]  
参考文章：

https://www.cnblogs.com/dalt/p/8306355.html

https://www.gamedev.net/reference/articles/article2003.asp

https://www.cnblogs.com/leafsblogowo/p/12749535.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70_pic_center]: /images/20210920/8f862cef77934c3d9635e55e957641d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210920/b7026cda3db34cd2b903efd165ba21e3.png