【转】K短路

K短路 用dijsktra+A*启发式搜索

当点v第K次出堆的时候,这时候求得的路径是k短路。
A*算法有一个启发式函数f(p)=g(p)+h(p), 即评估函数=当前值+当前位置到终点的最短距离
g(p):当前从s到p点所走的路径长度,h(p)就是点p到目的点t的最短距离。
f(p)就是当前路径从s走到p在从p到t的所走距离。
步骤:
1>求出h(p)。将有向边反向,求出目的点t到所有点的最短距离,用dijkstra算法
2>将原点s加入优先队列中
3>优先队列取出f(p)最小的一个点p
如果p==t,并且出来的次数恰好是k次,那么算法结束
否则,如果p出来的次数多余k次,就不用再进入队列中
否则遍历p相邻的边,加入优先队列中
注意:如果s==t,那么求得k短路应该变成k++;

原文地址:https://www.cnblogs.com/hoskey/p/3884141.html