时序最短路径算法  

Temporal Shortest Path Algorithm

作　　者：邓冬梅[1] 王冠楠[1] 朱建[1] 高辉[1] 陈端兵[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机科学》2014年第6期185-187,230,共4页Computer Science

摘　　要：最短路径是指网络中两结点间阻碍强度最小的一条路径。传统的最短路径是在静态网络上进行研究的,然而现实生活中很多网络是动态的、有时序性的,因此传统的最短路径算法并不能用于解决所有最短路径问题。为了寻找时序网络上的最短路径,在Dijkstra算法思想基础上,提出一种时序最短路径的精确算法。文中利用严格的数学推导证明了本算法的可行性,并通过对构建的网络做实证分析验证了算法的正确性。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 correcmess of the algorithm by mathematical derivation and verified the feasibility of the algorithm on a constructed network.

关 键 词：时序网络 最短路径 DIJKSTRA算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]