前K条最短路径算法.doc

注：为了简便我这里只列出算法的步骤和伪代码，详细的数学证明请参见相关论文。C+代码的算法实现可以在我的sourceforge目录/projects/ksp下载使用。特别要指出的是葡萄牙教授Martins对此算法有深入研究，发表了为数众多的相关论文，我这里采用的也是基于他早期提出的deletion algorithm。Martins的Fortran代码可以在这个网站http:/www.mat.uc.pt/eqvm/下载，同时这个网站还提供大量相关论文和文献。在此我谨向Martins教授致以敬意。前k条最短路径算法戴维编译一、算法说明Deletion Algorithm删除算法的核心是通过在有向图中已有的最短路径上删除某条弧，并寻找替换的弧来寻找下一条可选的最短路径。删除算法实际上是通过在有向图中增加附加节点和相应的弧来实现的。算法描述如下：1利用Dijkstra算法求得有向图(N,A)中以开始节点s为根的最短路径树（注意，这里的最短路径树并不是最小生成树，因为Dijkstra算法并不保证能生成最小生成树），标记从开始节点s到结束节点t之间的最短路径为pk，k=1。2如果k小于要求的最短路径的最大数目K，并且仍然有候选路径存在，令当前路径p=pk，转3。否则，程序结束。3找出当前路径p中从第一个节点开始的入度大于1的第一个节点，记为nh。如果nh的扩展节点nh不在节点集N中，则转4，否则找出路径p中nh后面所有节点中，其对应的扩展节点不在N中的第一个节点，记为ni，转5。4为节点nh构建一个扩展节点nh，并把其添加到集合N中，同时从图(N,A)中所有nh的前驱节点连接一条到nh的弧，弧对应的权重不变，添加这些弧到弧集A中，但nh在p中的前一个节点nh-1除外。计算从开始节点s到nh的最短路径，并记ninh+1。5对于p中从ni开始的所有后续节点，不妨记为nj，依次执行如下操作：5.1添加nj的扩展节点nj到节点集合N中。5.2除了路径p中nj的前一个节点nj-1外，分别连接一条从nj前驱节点到其扩展节点nj的弧，弧上的权值保持不变，并把这些弧添加到弧集A中。另外，如果p中nj的前一个节点nj-1具有扩展节点nj-1的话，也需要连接一条从nj-1到nj的弧，权值和弧(nj-1, nj)的权值相等。5.3计算从开始节点s到nj的最短路径。6更新当前最短路径树，求得从开始节点s到结束节点的当前扩展节点t(k)之间的最短路径为第k条最短路径，令k=k+1，转2继续。在上述步骤4、5、6中均需要计算从开始节点到当前扩展节点的最短路径，因为程序开始时便生成了以开始节点为根的最短路径树，那么只要在扩充节点时，记录下每个新节点相对于开始节点的最短路径中其前一个节点编号以及从开始节点到当前节点的最短路径长度，就可以很容易求得任意时刻有向图中从开始节点到结束节点（或其扩充节点）之间的最短路径。扩展节点：上一条最短路径上的节点可能会在求取下一条最短路径的过程中进行扩展，也就是在上次节点集合的基础上增加相应的新节点，这些新的节点均称为扩展节点，其会继承被扩展结点的邻接边关系（具体请参见上述步骤4，5）。一个扩展节点仍然可能会在求取下一条最短路径的时候进行扩展，表现在示例图中就是在一个节点标记后面加一撇表示是在原始节点上扩展，加两撇表示是在上次扩展节点上再扩展，依次类推。前驱节点：就是最短路径中某个节点的前一个节点。二、算法示例下面以图1所示网络图为例，根据上述算法，分别求得其第k条最短路径，求解过程中有向图的变化情况如图15所示，粗体路径表示当前状态下的最短路径，不同类型的圈表示不同阶段生成的节点。图1 k=1时的最短路径图2 k=2时的最短路径图3 k=3时的最短路径图4 k=4时的最短路径图5 k=5时的最短路径参考文献：这个算法在70年代就提出来了，其间历经完善，发表的论文也是五花八门，为了能让初次接触此算法的人有个系统的认识，我这里列举了这个算法在近10多年发展过程中几篇有代表性的论文。1. J.A. Azevedo, J.J.E.R.S. Madeira, E.Q.V. Martins and F.M.A. Pires, A shortest paths ranking algorithm, (1990), Proceedings of the Annual Conference AIRO90, Models and Methods for Decision Support, Operational Research Society of Italy, 1001-1011.90这篇论文阐述了基于删除算法(deletion algorithm)的原理及方法，并指出了解决此类问题的三类算法，对其中删除算法以及基于最优化原理(Principle of Optimality)的算法进行了实验比较。2. E.Q.V. Martins and J.L.E. Santos. A new shortest paths ranking algorithm. Investigacao Operacional, 20:(1):47-62,2000.Martins在他99年这篇文章中对删除算法进行了改进，提出了MS Algorithm，实际上除了数据结构上的变化外，算法没有做实质性的改动。不过对于要从实现上来优化算法的人来说，当然是值得一看的。3. E.Q.V. Martins. A new improvement for a k shortest paths algorithm. 2000。（忘了出处了，不好意思）Martins随后又在他的这篇论文中改进了MS Algorithm，并依次详细列举了对早期的删除算法的逐步改进过程，所以这篇文章也是值得一读的。同样，这次改进也是从数据结构角度来改进算法效率的。4. Victor M. Jimenez and Andres Marzal. Computing the k shortest paths: A new algorithm and a experimental comparison. 1999. （忘了出处了，不好意思）终于在这篇文章中有人提出了新的算法-递归枚举算法(REA, Recursive Enumeration Algorithm)。论文中分别对新的算法和Martins的算法MSA以及另外一个叫做Eppstein的人的算法(EA)进行了详细的实验比较。我之所以选择Martins的算法也是因为这篇文章对这些算法的对比实验表明，MSA算法在节点小于2000的情况下表现不错，加之MSA简明易懂并且处在不停的完善中:)。下面是其他相关的论文，好多哦，不过还是建议你访问Martins教授的网站。Copyright戴维 2006.5于北京相关论文：1 A. Aggarwal, B. Schieber, and T. Tokuyama. Finding a minimum weight K-link path in graphswith Monge property and applications. Proc. 9th Symp. Computational Geometry, pp. 189197.Assoc. for Computing Machinery, 1993.2 R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan. Faster algorithms for the shortest pathproblem. J. Assoc. Comput. Mach. 37:213223. Assoc. for Computing Machinery, 1990.3 J. A. Azevedo, M. E. O. Santos Costa, J. J. E. R. Silvestre Madeira, and E. Q. V. Martins. Analgorithm for the ranking of shortest paths. Eur. J. Operational Research 69:97106, 1993.4 A. Bako. All paths in an activity network. Mathematische Operationsforschung und Statistik7:851858, 1976.5 A. Bako and P. Kas. Determining the k-th shortest path by matrix method. Szigma 10:6166,1977. In Hungarian.6 R. E. Bellman. On a routing problem. Quart. Appl. Math. 16:8790, 1958.7 A.W. Brander and M. C. Sinclair. A comparative study of k-shortest path algorithms. Proc. 11thUK Performance Engineering Worksh. for Computer and Telecommunications Systems, September1995.8 T. H. Byers and M. S.Waterman. Determining all optimal and near-optimal solutions when solvingshortest path problems by dynamic programming. Operations Research 32:13811384, 1984.9 P. Carraresi and C. Sodini. A binary enumeration tree to find K shortest paths. Proc. 7thSymp. Operations Research, pp. 177188. Athenaum/Hain/Hanstein, Methods of Operations Research45, 1983.10 G.-H. Chen and Y.-C. Hung. Algorithms for the constrained quickest path problem and the enumerationof quickest paths. Computers and Operations Research 21:113118, 1994.11 Y. L. Chen. An algorithm for finding the k quickest paths in a network. Computers and OperationsResearch 20:5965, 1993.12 Y. L. Chen. Finding the k quickest simple paths in a network. Information Processing Letters50:8992, 1994.13 E. I. Chong, S. R. Maddila, and S. T. Morley. On finding single-source single-destination k shortestpaths. Proc. 7th Int. Conf. Computing and Information, July 1995.http:/phoenix.trentu.ca/jci/papers/icci95/A206/P001.html.14 A. Consiglio and A. Pecorella. Using simulated annealing to solve the K-shortest path problem.Proc. Conf. Italian Assoc. Operations Research, September 1995.15 Y. Dai, H. Imai, K. Iwano, and N. Katoh. How to treat delete requests in semi-online problems.Proc. 4th Int. Symp. Algorithms and Computation, pp. 4857. Springer Verlag, Lecture Notes inComputer Science 762, 1993.16 M. T. Dickerson and D. Eppstein. Algorithms for proximity problems in higher dimensions. ComputationalGeometry Theory and Applications 5:277291, 1996.17 S. E. Dreyfus. An appraisal of some shortest path algorithms. Operations Research 17:395412,1969.18 El-Amin and Al-Ghamdi. An expert system for transmission line route selection. Int. PowerEngineering Conf, vol. 2, pp. 697702. Nanyang Technol. Univ, Singapore, 1993.19 D. Eppstein. Finding common ancestors and disjoint paths in DAGs. Tech. Rep. 95-52, Univ. ofCalifornia, Irvine, Dept. Information and Computer Science, 1995.20 D. Eppstein. Ten algorithms for Egyptian fractions. Mathematica in Education and Research4(2):515, 1995./eppstein/numth/egypt/.21 D. Eppstein, Z. Galil, and G. F. Italiano. Improved sparsification. Tech. Rep. 93-20, Univ. ofCalifornia, Irvine, Dept. Information and Computer Science, 1993.:80/TR/UCI:ICS-TR-93-20.22 D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification A technique for speedingup dynamic graph algorithms. Proc. 33rd Symp. Foundations of Computer Science, pp. 6069. IEEE, 1992.23 L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ,1962.2324 B. L. Fox. k-th shortest paths and applications to the probabilistic networks. ORSA/TIMS JointNational Mtg., vol. 23, p. B263, 1975.25 G. N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallestspanning trees. Proc. 32nd Symp. Foundations of Computer Science, pp. 632641. IEEE, 1991.26 G. N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation104:197214, 1993.27 M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimizationalgorithms. J. Assoc. Comput. Mach. 34:596615. Assoc. for Computing Machinery, 1987.28 M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning treesand shortest paths. Proc. 31st Symp. Foundations of Computer Science, pp. 719725. IEEE, 1990.29 A. V. Goldberg. Scaling algorithms for the shortest paths problem. SIAM J. Computing24(3):494504. Soc. Industrial and Applied Math., June 1995.30 V. Hatzivassiloglou and K. Knight. Unification-based glossing. Proc. 14th Int. Joint Conf.Artificial Intelligence, pp. 13821389. Morgan-Kaufmann, August 1995./natural-language/mt/ijcai95-glosser.ps.31 G. J. Horne. Finding the K least cost paths in an acyclic activity network. J. Operational ResearchSoc. 31:443448, 1980.32 L.-M. Jin and S.-P. Chan. An electrical method for finding suboptimal routes. Int. Symp. Circuitsand Systems, vol. 2, pp. 935938. IEEE, 1989.33 D. B. Johnson. A priority queue in which initialization and queue operations take O.log log D/time. Mathematical Systems Theory 15:295309, 1982.34 N. Katoh, T. Ibaraki, and H. Mine. An O.Kn2/ algorithm for K shortest simple paths in an undirectedgraph with nonnegative arc length. Trans. Inst. Electronics and Communication Engineersof Japan E61:971972, 1978.35 N. Katoh, T. Ibaraki, and H. Mine. An efficient algorithm for K shortest simple paths. Networks12(4):411427, 1982.36 P. N. Klein, S. Rao, M. H. Rauch, and S. Subramanian. Faster shortest-path algorithms for planargraphs. Proc. 26th Symp. Theory of Computing, pp. 2737. Assoc. for Computing Machinery,1994.37 N. Kumar and R. K. Ghosh. Parallel algorithm for finding first K shortest paths. ComputerScience and Informatics 24(3):2128, September 1994.38 A. G. Law and A. Rezazadeh. Computing the K-shortest paths, under nonnegative weighting.Proc. 22nd Manitoba Conf. Numerical Mathematics and Computing, pp. 277280, Congr. Numer.92, 1993.39 E. L. Lawler. A procedure for computing the K best solutions to discrete optimization problemsand its application to the shortest path problem. Management Science 18:401405, 1972.2440 E. L. Lawler. Comment on computing the k shortest paths in a graph. Commun. Assoc. Comput.Mach. 20:603604. Assoc. for Computing Machinery, 1977.41 E. Q. V. Martins. An algorithm for ranking paths that may contain cycles. Eur. J. OperationalResearch 18(1):123130, 1984.42 S.-P. Miaou and S.-M. Chin. Computing k-shortest path for nuclear spent fuel highway transportation.Eur. J. Operational Research 53:6480, 1991.43 E. Minieka. On computing sets of shortest paths in a graph. Commun. Assoc. Comput. Mach.17:351353. Assoc. for Computing Machinery, 1974.44 E. Minieka. The K-th shortest path problem. ORSA/TIMS Joint National Mtg., vol. 23, p. B/116,1975.45 E. Minieka and D. R. Shier. A note on an algebra for the k best routes in a network. J. Inst.Mathematics and Its Applications 11:145149, 1973.46 D. Naor and D. Brutlag. On near-optimal alignments of biological sequences. J. ComputationalBiology 1(4):349366, 1994./brutlag/Publications/naor94.html.47 A. Perko. Implementation of algorithms for K shortest loopless paths. Networks 16:149160,1986.48 Y. Perl and Y. Shiloach. Finding two disjoint paths between two pairs of vertices in a graph. J.Assoc. Comput. Mach. 25:19. Assoc. for Computing Machinery, 1978.49 J. B. Rosen, S.-Z. Sun, and G.-L. Xue. Algorithms for the quickest path problem and the enumerationof quickest paths. Computers and Operations Research 18:579584, 1991.50 E. Ruppert. Finding the k shortest paths in parallel. Proc. 14th Symp. Theoretical Aspects ofComputer Science, February 1997.51 T. Shibuya. Finding the k shortest paths by AI search techniques. Cooperative Research Reportsin Modeling and Algorithms 7(77):212222. Inst. of Statical Mathematics, March 1995.52 T. Shibuya, T. Ikeda, H. Imai, S. Nishimura, H. Shimoura, and K. Tenmoku. Finding a realisticdetour by AI search techniques. Proc. 2nd Intelligent Transportation Systems, vol. 4, pp. 20372044, November 1995.http:/naomi.is.s.u-tokyo.ac.jp/papers/navigation/suboptimal-routes/ITS%95/its.ps.gz.53 T. Shibuya and H. Imai. Enumerating suboptimal alignments of multiple biological sequencesefficiently. Proc. 2nd Pacific Symp. Biocomputing, pp. 409420, January 1997./people/altman/psb97/shibuya.pdf.54 T. Shibuya and H. Imai. New flexible approaches for multiple sequence alignment. Proc. 1stInt. Conf. Computational Molecular Biology, pp. 267276. Assoc. for Computing Machinery,January 1997.http:/naomi.is.s.u-tokyo.ac.jp/papers/genome/recomb97.ps.gz.55 T. Shibuya, H. Imai, S. Nishimura, H. Shimoura, and K. Tenmoku. Detour queries in geographicaldatabases for navigation and related algorithm animations. Proc. Int. Symp. CooperativeDatabase Systems for Advanced Applications, vol. 2, pp. 333340, December 1996. http:/naomi.is.s.u-tokyo.ac.jp/papers/databases/codas96.ps.gz.2556 D. R. Shier. Algorithms for finding the k shortest paths in a network. ORSA/TIMS Joint NationalMtg., p. 115, 1976.57 D. R. Shier. Iterative methods for determining the k shortest paths in a network. Networks6(3):205229, 1976.58 D. R. Shier. On algorithms for finding the k shortest paths in a network. Networks 9(3):195214,1979.59 C. C. Skicism and B. L. Golden. Solving k-shortest and constrained shortest path problems ef-ficiently. Network Optimization and Applications, pp. 249282. Baltzer Science Publishers, Annalsof Operations R