K短路算法相关

昨天中午打饭等待时无聊，想了一下求K短路的多项式解法。在此之前大概了解过知道可以用A*解。具体做法是先从T做一次Dijkstra，用各点到T的最短路径作为估价函数。从S开始A*，在寻找过程中，使每个点都能被访问多次（即去掉close表），并且每次访问到一个点v并不需要到open表去查找判重，直接放到open中即可，那么第k次从open表中取出点T即是S-T的k短路（via Richard）。

由于之前明白了可以用堆来维护单调队列，通过单调队列的合并来求背包问题的前k优解，感觉应该也可适用于最短路算法。比如SPFA，使用单调队列来维护第k优值，判断是否在队列中时记录多一个最优值属性即可。在网上看到有人说这一算法的时间复杂度是O(KVE)的，但我不知道如何证明。

一开始没深入想，认为Dijkstra的处理只需要像背包那样每次更新最优路径时进行单调队列的合并即可。后来发现这样子会遗漏一部分路径。于是为了保证不遗漏路径，单调队列的处理会比较麻烦一些。可以证明若每个点出堆的次数都为k则可保证求得第k优路径。单调队列需要满足能够同时维护当前最优解（用于选取出堆点）和第k优解的值，我想到的解决方案是用一个min heap和max heap（要多记录一个信息，每个节点在min heap中的位置）来维护。后来在搜索过程中发现已经有了满足这一性质的堆：min-max heap和Deap，也可直接使用这两种数据结构进行维护。

不过以上两种算法都只能适用于k数值较小时，若k数值较大则只能用A*或转化为用二分判可行性的问题（参考SGU上某题）了。