计算机科学 ›› 2014, Vol. 41 ›› Issue (6): 185-187.doi: 10.11896/j.issn.1002-137X.2014.06.036
邓冬梅,王冠楠,朱建,高辉,陈端兵
DENG Dong-mei,WANG Guan-nan,ZHU Jian,GAO Hui and CHEN Duan-bing
摘要： 最短路径是指网络中两结点间阻碍强度最小的一条路径。传统的最短路径是在静态网络上进行研究的,然而现实生活中很多网络是动态的、有时序性的,因此传统的最短路径算法并不能用于解决所有最短路径问题。为了寻找时序网络上的最短路径,在Dijkstra算法思想基础上,提出一种时序最短路径的精确算法。文中利用严格的数学推导证明了本算法的可行性,并通过对构建的网络做实证分析验证了算法的正确性。
| [1] 荣玮．基于道路网的最短路径算法与实现[D]．武汉:武汉理工大学,2005 [2] 涂海丽．最短路径算法及其应用探讨[J]．科技广场,2011(9) [3] 吴莲．基于城市道路网的遗传最短路径算法研究[D]．南京:南京理工大学,2010 [4] 于东凯,刘玉树．基于平面图的最短路径算法的研究[J]．北京理工大学学报,2003,21(1) [5] 董俊,黄传河．改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J]．计算机科学,2012,39(10) [6] 艾菊梅,周书民,陆玲．基于WebGIS公交查询平台与移动增值服务[J]．微计算机信息,2007(10) [7] SCHULTESD．Route planning in road networks[D]．Karlsruhe:UniversittFridericiana,2008 [8] Fu L．Real-time vehicle routing and scheduling in dynamic and stochastic traffic networks[D]．Edmonton,Alberta:University of Alberta,1996 [9] Nicosia G,Oriolo G．An approximate A* algorithm and its application to the SCS problem[J]．Theoretical Computer Science,2003,290(3):2021-2029 [10] Bander J L,White C C．A heuristic search algorithm for path determination with learning[J]．IEEE Transactions on Systems,Man,and Cybernetics,Part A,1998,28(1):131-134 [11] 宋青,汪小帆．最短路径算法加速技术研究综述[J].电子科技大学学报,2012(2) [12] 唐晋韬,王挺,王戟．适合复杂网络分析的最短路径近似算法[J]．中国:软件学报,2011,22(10) [13] Rajk P,Jari S．Path lengths,correlations,and centrality in temporal networks[J]．Finland:Phys．Rev．E 84,2011:016105 [14] Dijkstra E W．A note on two problems in connexion with graphs[J]．Numerical Mathematics,1959,1(1):269-271 [15] 严蔚敏,吴伟民．数据结构[M]．北京:清华大学出版社,2001,186-190 [16] 张先迪,李正良．图论及其应用[M]．北京:高等教育出版社,2005 [17] Petter H,Jari S．Temporal networks[J]．Phys．Rep,2012,519:97-125 |
| No related articles found! |
|
||
首页