专题

第K短路(A*(astar)算法)

作者:admin 来源:原创 时间:2020年04月04日 02:10:08浏览:

  给定一张N个点(编号1,2…N),M条边的有向图,求从终点S到终点T的第K短路的长度,门路许可重复经过点或边。

  留心:?每条最短路中至少要包罗一条边。

  输入格局

  第一行包罗两个整数N和M。

  接上去M行,每行包罗三个整数A,B和L,表现点A与点B之间存在有向边,且边长为L。

  最后一行包罗三个整数S,T和K,辨别表现终点S,终点T和第K短路。

  输入格局

  输入占一行,包罗一个整数,表现第K短路的长度,假设第K短路不存在,则输入“-1”。

  数据范围

  1≤S,T≤N≤1000

  0≤M≤105

  1≤K≤1000

  1≤L≤100

  输入样例:

  输入样例:

  ?思路:A*算法就是在bfs上加了一个启发函数,也就是一个距离的估值,从而使搜刮更直接,更准确,防止了很多不用要的搜刮,A*算法的一条定理,只需估计值f(s)<=实践距离d(s),每次从优先队列中bfs之前取出的用来扩大的就是以后最小距离,因为最短距离必然<=真实距离,所以可以:

  1、用终点T作为dijkstra的终点在反向图中跑一遍dijkstra算出每个点到终点的最短距离,作为阿谁点的估值。

  2、用astar算法,然后依据估值排序(把估计值作为pair的first放到优先队列便可以完成按估值排序了),从S末尾bfs,每次的取出的就是最短,第k次抵达T点就是第K短路了。

  完整代码:

  ?

(来源:原创   admin)  

1.皇冠体育365遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本网的原创文章,请转载时务必注明文章作者和"来源:皇冠体育365",不尊重原创的行为皇冠体育365或将追究责任;3.作者投稿可能会经皇冠体育365编辑修改或补充。

阅读延展