Computer Science ›› 2014, Vol. 41 ›› Issue (6): 185-187.doi: 10.11896/j.issn.1002-137X.2014.06.036

Previous Articles     Next Articles

Temporal Shortest Path Algorithm

DENG Dong-mei,WANG Guan-nan,ZHU Jian,GAO Hui and CHEN Duan-bing   

  • Online:2018-11-14 Published:2018-11-14

Abstract: The shortest path is a path which has the least hinder strength between two nodes in the specified network.Traditionally,it is studied on static network,but many networks are dynamic and temporal in real life.So the traditional algorithms can’t solve all problems about shortest path.This paper presented a precision algorithm to find the temporal shortest path based on the Dijkstra’s algorithm.It proved the correctness of the algorithm by mathematical derivation and verified the feasibility of the algorithm on a constructed network.

Key words: Temporal network,Shortest path,Dijkstra’s algorithm

[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:UniversittFridericiana,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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!