计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
6期
185-187,230
,共4页
邓冬梅%王冠楠%朱建%高辉%陈端兵
鄧鼕梅%王冠楠%硃建%高輝%陳耑兵
산동매%왕관남%주건%고휘%진단병
时序网络%最短路径%Dijkstra算法
時序網絡%最短路徑%Dijkstra算法
시서망락%최단로경%Dijkstra산법
Temporal network%Shortest path%Dijkstra's algorithm
最短路径是指网络中两结点间阻碍强度最小的一条路径.传统的最短路径是在静态网络上进行研究的,然而现实生活中很多网络是动态的、有时序性的,因此传统的最短路径算法并不能用于解决所有最短路径问题.为了寻找时序网络上的最短路径,在Dijkstra算法思想基础上,提出一种时序最短路径的精确算法.文中利用严格的数学推导证明了本算法的可行性,并通过对构建的网络做实证分析验证了算法的正确性.
最短路徑是指網絡中兩結點間阻礙彊度最小的一條路徑.傳統的最短路徑是在靜態網絡上進行研究的,然而現實生活中很多網絡是動態的、有時序性的,因此傳統的最短路徑算法併不能用于解決所有最短路徑問題.為瞭尋找時序網絡上的最短路徑,在Dijkstra算法思想基礎上,提齣一種時序最短路徑的精確算法.文中利用嚴格的數學推導證明瞭本算法的可行性,併通過對構建的網絡做實證分析驗證瞭算法的正確性.
최단로경시지망락중량결점간조애강도최소적일조로경.전통적최단로경시재정태망락상진행연구적,연이현실생활중흔다망락시동태적、유시서성적,인차전통적최단로경산법병불능용우해결소유최단로경문제.위료심조시서망락상적최단로경,재Dijkstra산법사상기출상,제출일충시서최단로경적정학산법.문중이용엄격적수학추도증명료본산법적가행성,병통과대구건적망락주실증분석험증료산법적정학성.
