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上某题）了。

ZJU/ZOJ 1942 Frogger 解题报告

题目大意是求路径中两点最大距离最小的路径并输出在这条路径中两点的最大距离。

只需对Dijkstra算法稍作改进即可，将路径更新的规则修改为dis[i]=min(dis[i],max(dis[now],dist[now,i]));其中dis[i]表示从1到i的已知最优两点距离，now表示当前用来更新的节点，dist[now,i]表示now与i的距离。

3064594 2008-09-09 13:56:21 Accepted 1942 FPC 00:00.00 728K IwfWcf

ZJU/ZOJ 1456 Minimum Transport Cost 解题报告

求给出的两点间的最短路径，如果有多条最短路径要求输出字典序最小的。

由于给的是稠密图所以首选朴素的Dijkstra算法，但是由于要问多个点对之间的最短路径，所以实际上用Floyd的效率更高。注意字典序最小这一限制条件的处理方法，因为对这一条件的处理错误WA了很久……我的处理方法是用next[i,j]表示从i到j的短路径的最近中间点，遇到经某个中间点与已知最短路径距离相等时倒推求出第一个不同的点，比较大小来判断是否进行next数组的更新操作。

3009127 2008-07-27 18:10:39 Accepted 1456 FPC 00:00.01 424K IwfWcf