K短路¶
问题描述¶
给定一个有\(n\)个结点，\(m\)条边的有向图，求从\(s\)到\(t\)的所有不同路径中的第\(k\)短路径的长度。
A*算法¶
该算法定义了一个对当前状态\(x\)的估价函数\(f\)： $$ f(x)=g(x)+h(x) $$
-
\(f(x)\)是当前状态的总代价
-
\(g(x)\)是初始状态到当前状态的实际代价
-
\(h(x)\)是当前当前状态到目标状态的**估计**代价
一般而言，\(h(x)\)的计算方式可以由自己决定，但是需要根据以下原则：
-
必须要不小于真实值，避免答案错误
-
尽量向真实值靠拢，提高算法效率
每次取出\(f(x)\)的最优状态\(x\)，扩展其所有子状态，可以用**优先队列**来维护。
在求解k最短路问题时，令\(h(x)\)为从当前结点到达终点\(t\)的最短路径长度。由于涉及的距离函数和估价函数，每个状态需要记录两个值——当前到达的结点\(x\)和已经走过的距离\(g(x)\)。
可以通过反向图上对结点\(t\)跑单源最短路预处理对每个结点的这个值。
步骤：
- 开始我们将初始状态\((s,0)\)加入优先队列。
- 每次取出估价函数最小的一个状态，枚举该状态到达的结点\(x\)的所有出边，将对应的子状态加入优先队列。
- 当我们访问到一个结点第\(k\)次时，对应的状态的\(g(x)\)就是从\(x\)到该结点的第\(k\)短路。
优化：
由于只需要求出初始状态到目标结点的第\(k\)短路，所以已经取出的状态到达一个结点的次数大于\(k\)时，可以不扩展其子状态。
参考¶
Easy A* (star) Pathfinding. Today we’ll being going over the A*… | by Nicholas Swift | Medium