交通网络k-短路径与最小支撑树问题  

K-shortest paths and minimum spanning tree in traffic network

作　　者：陈京荣[1] 俞建宁[1] 李引珍[2] 

机构地区：[1]兰州交通大学数理学院,甘肃兰州730070 [2]兰州交通大学交通运输学院,甘肃兰州730070

出　　处：《长安大学学报（自然科学版）》2014年第3期133-136,共4页Journal of Chang’an University(Natural Science Edition)

基　　金：国家自然科学基金项目(61164003);教育部博士点基金项目(20136204120007);甘肃省自然科学基金项目(1308RJZA128)

摘　　要：为了给交通管理部门提供多个路径诱导信息,基于经典的最短路径算法——Dijkstra算法,研究了赋权交通网络的k-短路径问题。k-短路径问题是在网络G中求出给定起讫点对之间的k条路径P1,P2,…,Pk,满足W(P1)≤W(P2)≤…≤W(Pk),其中W(*)表示路径*的权值。在网络G的基础上,通过对G的点、边重新划分以及对边上的权值重新赋值,构造出了1个新的网络G′并讨论了它的几个性质。从而将G的k-短路径问题转换为求解G′的最小支撑树问题,进一步,最小支撑树问题又等价于求G′中一条边的权值。研究结果表明:由于最小支撑树问题具有多项式算法,得到关于k-短路径问题的多项式算法,其时间复杂性为O(k(m+nlg(n))),m和n为G的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。In order to provide route guidance information to traffic departments,k-shortest paths were studied based on Dijkstra algorithm.The k-shortest paths problem is to get k paths P1,P2,…,Pkfor a given pair of points and meet the criteria W（P1）≤W（P2）≤…≤W（Pk）,where W（＊）denotes the weight of path＊.By partitioning the vertex set and the edge set of G,and reassigning the weight for each edge,a new network G′was constructed from G.Then the kshortest paths problem of G was converted into the minimum spanning tree（MST）problem of G′.MST problem became equal to computing an edge＇s weight in G′.The results show that based on the polynomial algorithm of MST problem,an polynomial algorithm for the k-shortest paths problem is obtained and the time complexity is O（k（m＋nlog（n）））,where m and n denote the number of edges and nodes of Grespectively.In the end,an illustrative example verifies the concrete progress and the feasibility of the algorithm.

关 键 词：交通工程 交通网络 k-短路径 最小支撑树 DIJKSTRA算法 

分 类 号：U116.2[交通运输工程]