K短路

其实这个才是最短路的一个非常好的应用。那么下面我们就来讲一讲具体如何实现吧。

先确保自己已经熟练掌握了两种最短路的求解方法！！！

这里有传送门：

然后我们先大体讲一讲思路，第k短路顾名思义就是我们要找到反正不是最短的一条路，那怎么办呢？我们这个时候就会发现我们不能像实现各种最短路算法的方法一样刷dis刷出第k短路，那么这个时候又怎么办呢，那么我们的A*算法就闪亮登场了！

A*又叫启发式搜索，启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。

这里给大家放两个照片，俗话说的好没有对比就没有伤害。
我们直观对比一下普通搜法和A*搜法的差异（灰色是障碍物）

因为图片有一些问题，所以这里并没有展出

这里有个传送门：大家可以看一下里面有图有真相：
戳我

好了，我们下面来讲一讲A_star是如何实现K短路的吧。

首先，我们要先存储两个图一个正图一个反图，用反图跑一遍最短路（spfa或Dijsktra随你便）记录好每一个点到达最后一个点的距离（dis数组存储）然后干好这些事情以后我们可以开始我们的A_star算法了！

大体思路其实是这样的，我们用所存储的条件从dis[1]开始push到优先队列中去然后每一次对优先队列中的边进行松弛操作即用当前的值减去当前位置的dis+正图到下一个点的连线+下一个点的dis

		q.push((sd){edge[now.num][i].num,now.len-dis[now.num]+edge[now.num][i].len+dis[edge[now.num][i].num]});

大家应该没有什么理解上的问题了，下面我们上一篇代码！！！

代码如下：（注意标注了important的地方！）

#include<bits/stdc++.h>
using namespace std;
const int maxd=5010;
int dis[maxd];
bool vis[maxd];
int n,m,e;
struct sd {
    int num, len;
    bool operator < (const sd &other) const {
        return len > other.len;
    }
};
vector<sd> edge[maxd],redge[maxd];

void spfa()
{
	memset(dis,127,sizeof(dis));
	dis[e]=0;
	queue<int> q;
	q.push(e);
	vis[e]=true;
	while(!q.empty())
	{
		int now=q.front(); q.pop(); vis[now]=false;
		for(int i=redge[now].size()-1;i>=0;--i)
		{
			if(dis[redge[now][i].num]>dis[now]+redge[now][i].len)
			dis[redge[now][i].num]=dis[now]+redge[now][i].len;
			if(!vis[redge[now][i].num])
			{
				vis[redge[now][i].num]=true;
				q.push(redge[now][i].num);
			}
		}
	}
}
int A_star(int cnt)
{
	int ccnt=0;
	priority_queue<sd> q;
	q.push((sd){1,dis[1]});//important
	while(!q.empty())
	{
		sd now=q.top();
		q.pop();
		if(now.num==e)
		{
			ccnt++;
			if(cnt==ccnt)
			{
				return now.len;
			}
			continue;//important
		}
		for(int i=edge[now.num].size()-1;i>=0;--i)
		{
			q.push((sd){edge[now.num][i].num,now.len-dis[now.num]+edge[now.num][i].len+dis[edge[now.num][i].num]});//important
		}
	}
}
int main()
{
	int us;
	scanf("%d%d%d",&n,&m,&e);
	scanf("%d",&us);
	int a,b,c;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		edge[a].push_back((sd){b,c});
		redge[b].push_back((sd){a,c});
	}
	spfa();
	if(us==1) goto flag;
	cout<<A_star(us); return 0;
	flag:
	printf("%d",dis[1]);
	return 0;
}
/*
4 5 4
3
1 2 4
2 3 2
1 3 5
3 4 6
2 4 3
*/

谢谢采纳！