终于到了该说再见的时候了，虽然K短路算法远远不止我这几篇文章所能涵盖。但毕竟任何blog只是代表了作者个人的理解，或许对于某些人有一些提示，其作用就尽到了，因此，这最后一篇并非是一个了结，而是读论文的导引。

先读读历史。关于K短路算法的研究，在60年代中期就开始就有论文发表了（大概就是Dijkstra算法发表后不久），其思想主要就是我在第一篇文章和以前的文章中所阐述的：扩展标号系列算法。75年左右，Yen就提出了文章2的偏离路算法，这是一个很大的进步，因为他发展出了一套全新的思路（但是正如我说过，它其实是A*的另一种表现形式）。80年代这一研究热似乎退了下来，这一时期的论文大多都是对前述算法的改进，或是实现上的，或是数据结构上的，至少我没有发现新的思想涌现出来。90年代，一下子从80年代的冷淡中爆发了，突然涌现出很多的研究者，其数量大大超过以前的总和，当然新的方法也是层出不穷（绝对不夸张，真的是能想到的什么怪方法都出来了，包括利用DNA计算，感兴趣的可以去网上搜），文章3就是其中一篇代表，另外著名的还有Eppstein算法，是目前所知的复杂度最低的算法（实际性能据多家指出并不如想像中高）。进入21世纪，这一研究又冷了下来，我只找到一篇文章提出的算法相对比较容易理解（当然，我没有仔细读毕），而总的来说数量和质量都有所下降。

我写这些文章的初衷是为了把一些简单高效的算法引入到ACM/ICPC中，虽然在这一行当，实现简单才是美，但这并不代表就不应该吸纳新的算法。当我在写文章2的时候，其实我还是有些犹豫，因为中间涉及到的平衡树等都是参赛者比较忌讳的东西（因为实现比较复杂，一般能不用尽量不用，况且那个地方用堆代替也不会损失很多性能），所以怕不会有人去关注。但后来当我读到Path Deletion算法的时候的确眼前一亮，因为其核心思想就是一个DP，实现非常简练，不高于在这一领域占统治地位的A*算法，而其性能也非常优秀，所以文章3是我最推荐的一篇。

Loopless算法似乎在实际应用中更多一些（当然拉，哪个路线规划者都不希望去一个地方两次），而我介绍的Yen算法也的确不是性能最优秀的。其实，我在文章4中开头也说过，Loopless只是Constrained Path（面向领域解决问题或许是未来研究的一个新方向──个人观点）中的一种，而后者或许才更接近实际，因为它允许你定义任意一种限制函数。2006年上海赛区的比赛就出现了一个该类问题（POJ3142），我目前还没找到好方法，所以留给大家来告诉我了，-_-。

本文随后附的论文就是我主要参考的文章，我推荐看这几篇是因为他们都基本上出自同一人之手，因此行文风格类似，利于缩短学习时间。

就这样吧，该系列文章到此也就全部结束了，不过我还会对它们进行维护，时不时做一些语言上的修补，当然在将来加入新算法也是可能的，毕竟这些文字是我目前发现在ICPC领域中关于K短路算法最全的介绍了，我当然愿意让它变得更完美。

Enjoy reading papers and hacking codes.

附：

所有的代码可以通过邮件frogxx@gmail.com 或POJ 站内信richardxx向我索取。

论文下载：KSP_papers