A star 算法：通过一个估价函数 $f(n)=g(n)+h(n)$ 来估计图中的当前点 $n$ 到终点的距离，并由此决定它的搜索方向。首先在反图上使用Spfa或Dijkstra求出所有点到终点的最短路径。估价函数：当前走过的距离 + 该点到终点的最短路长度。用堆（优先队列）维护，每次取出估价函数最小的一个点扩展。第 $k$ 次从堆中取出点 $T$，就是找到了 $T$ 的第 $k$ 短路。算法模板