第K短路

我最近在找最大流的题来练手,标题上明明写着是网络流习题汇总,打开链接一看却是第K短路POJ2449

第K短路

第K短路也是一个经典的问题。翻看了一下网上的教程,基本思路都是逆图SPFA+A*来处理。还有更复杂的优化了的算法,我没有仔细看。

A*算法需要的估计函数

f(x)=g(x)+h(x)f(x)=g(x)+h(x)

反向建图,预处理出A*的启发值h(x)h(x),这里h(x)h(x)选用的是到终点的距离,所以使用最短路算法来得到。

然后开始A搜索,f(x)f(x)较小的优先处理,终点t每出一次队就k--,直到k为0的时候,说明这个状态搜索过来的就是第k短路了,因为A算法保证了前面出队的一定就是更短的。

A*算法的延伸思考

为什么能保证先出队的一定是更短的?

如果定义从状态x到终点的实际距离为h(x)h'(x),要保证我们选择的h(x)h(x)满足h(x)h(x)h(x)\leq h'(x),这样实际在我们真的靠近结果的时候启发值不会带我们跑偏。

然后回到这个问题,前面出队的当然是最短的。从s出发到t的路径中有一条或者多条路径是最短的,在它们被广搜的时候估计出来的f(x)f(x)始终等于从st的距离。其他的路径的f(x)f(x)一定会更大,因为它们没有按照最短路来走,所以在广搜的时候自然会后出队。

A*与其他搜索的关系

  • 深搜:g(x)=0
  • 广搜:h(x)=0

问题的解决

我本想着用来练练手,可以直接水过,结果WA!我以为是我的SPFA出问题了,连忙找了一道SPFA模板题POJ3013,一写,还是WA!我找了一道更基础的POJ2387,这次终于AC了……

反回来看这道题的Discuss区域,发现在s==t的情况下,长度为0的路径是不被考虑为一条合法的路径的。那么只要加上:

if(s==t){
    k++;
}

就AC了!

16509367 sshockwave 2449 Accepted 7156K 141MS G++ 1933B 2017-01-22 13:56:33

avatar
Kerry Su