轨道交通因其造价高、投资大、工期长等因素的影响,整个城市轨道交通路网的建设过程中会涉及到不同的投资方、建设方和运营方。随着路网规模的不断扩大和线路交叉,形成了跨越不同运营线路的乘车情况,为了客观、公平、公正地把交易款划分给被乘运线路,产生了轨道交通清分系统。建立清分系统需要解决异线站点之间的换乘路径问题,即无向图中求解给定顶点对之间K条最优路径问题。在研究了求解K优路径问题的基本理论和2nd最优路径搜索算法的基础上,借助于“背离”路径的概念,提出了一种新的Kth最优路径搜索算法。通过K-1次2nd最短路径搜索算法的迭代,求解出网络中任意两个给定节点之间的Kth最优路径,由于2nd最短路径搜索算法在计算上的简单性,本算法同样具有简洁、快速的特点。使用斐波那契堆优化Dijkstra算法中的最小优先队列,使Dijkstra算法的性能达到最优。针对算法在搜索过程中产生的环路,在分析了删除边去环算法的基础上,提出用2nd算法的思想去环,在产生环路节点的背离路径中搜索次优路径作为新的背离路径,解决了算法的瓶颈问题,使整体路径求解算法的效率有了显著的提高。在此基础上,对算法所涉及到的数据结构进行了调整,用邻接多重表来存储路网结构图,用其MARK域标记节点所在的路径以判断是否存在环路。用固定长度的队列存储最终形成的路径,使不符合要求的路径尽早的排除,进一步提高算法的效率。该算法的时间复杂度为O(VlgV+E+K~*m~*t)。最后,结合上海轨道交通路网模型对算法进行了验证,证实了算法能够有效解决某些实际问题中大量节点连通图中K条渐次最优路径的问题。