求解K最短路径的改进Dijkstra算法

Solves K most short-path improvement Dijkstra algorithm

本文首先从轨道交通和常规交通的衔接规划的视角，阐述了求解K最短路径问题在公交线网优化中的意义。然后在Dijkstra最短路算法的基础上，创造性地引入了多个P标和多个T标来记录起点到该节点的K短路径及其上界，使改进后的算法成功求解K最短路径。最后用C语言对算法进行实现，并随机产生测试数据进行算法测试，测试结果表明了该算法的计算效率和应用前景。

This article first from the orbital transportation and the conventional transportation engagement plan angle of view, elaborated solves the K most short-path question to optimize in the public transportation wire the significance. Then most short-circuits in Dijkstra in the algorithm foundation,creatively has introduced many P sign and many T sign records the beginning to this node K short-path and the upper boundary,after makes the improvement the algorithm success to solve the K most short-path. Finally uses the C language to carry on the realization to the algorithm,and had the test data to carry on the algorithm test stochastically,the test resuit has indicated this algorithm counting yield and the application prospect.