A* 算法K短路算法

  所谓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*算法的要求。<

Ｋ短路算法codes.h