第k短路——A*算法

相信很多人都会求最短路,那么怎么求第k短路呢?我们可以直接爆搜,但是这样效率是很低的,这时我们可以用A*算法来解决这个问题。

令g[x]为当前的花费在这个问题里即为从1到x的路径长度,h[x]为估价函数在这里我们定为从x到n的距离是个不错的选择。然后我们设f[x]=g[x]+h[x]为x这点的估值。然后我们按f[x]排序,每次找f[x]最小的点进行扩展。

其中h[x]是可以预处理的,只需将边反向,然后从结束点跑一遍最短路即可。

具体代码及例题请点这里BZOJ1975: [Sdoi2010]魔法猪学院

点赞
  1. hgz说道:

    做题全靠自行脑补 :confused:
    17128884 99hgz 2449 Accepted 20372K 454MS C++ 2219B 2017-07-03 08:40:48
    顺便求个证明什么的
    还有a*求kth path是可以被卡掉的?

  2. foolish说道:

    首先k短路的实质是暴力,
    暴力你证明正确性的话比较强的。
    还有A*是玄学时间空间的,
    如果你想卡A*属于丧心病狂谢谢,
    k短路暂时没有更好的求法了(呵呵
    BZOJ上有一题就卡了A*基本所有人都打表。

    1. hekai说道:

      谢谢 :idea:

发表评论

您的电子邮箱地址不会被公开。