资 源 简 介
所谓K短路,就是从s到t的第K短的路,第1短就是最短路。
如何求第K短呢?有一种简单的方法是广度优先搜索,记录t出队列的次数,当t第k次出队列时,就是第k短路了。但点数过大时,入队列的节点过多,时间和空间复杂度都较高。
A*是在搜索中常用的优化,一种启发式搜索。简单的说,它可以用公式表示为f(n) = g(n) + f(n),其中,f(n)是从s经由节点n到t的估价函数,g(n)是在状态空间中从s到n的实际代价,h(n)是从n到t的最佳路径估计代价。在设计中,要保证h(n)<= n到t的实际代价,这一点很重要,h(n)越接近真实值,速度越快。
由于启发函数的作用,使得计算机在进行状态转移时尽量避开不可能产生最优解的分支,而选择相对较接近最优解的路径进行搜索,降低了时间和空间复杂度。
算法过程:
1. 将图反向,用dijstra+heap求出t到所有点的最短距离,目的是求所有点到点t的最短路,用dis[i]表示i到t的最短路,其实这就是A*的启发函数,显然:h(n)<= n到t的实际代价。
2. 定义估价函数。我们定义g(n)为从s到n所花费的代价,h(n)为dis[n],显然这符合A*算法的要求。<