交通网络k-短路径与最小支撑树问题 |
| |
引用本文: | 陈京荣,俞建宁,李引珍.交通网络k-短路径与最小支撑树问题[J].长安大学学报(自然科学版),2014(3). |
| |
作者姓名: | 陈京荣 俞建宁 李引珍 |
| |
作者单位: | 兰州交通大学数理学院;兰州交通大学交通运输学院; |
| |
基金项目: | 国家自然科学基金项目(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的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。
|
关 键 词: | 交通工程 交通网络 k-短路径 最小支撑树 Dijkstra算法 |
本文献已被 CNKI 等数据库收录! |
|