微计算机信息
微計算機信息
미계산궤신식
CONTROL & AUTOMATION
2009年
15期
164-166
,共3页
最短路径%迪杰斯特拉%弗洛伊德
最短路徑%迪傑斯特拉%弗洛伊德
최단로경%적걸사특랍%불락이덕
移动IPv6的路由寻址是一个最短路径优化问题,最著名的两种最短路径算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,这两种算法的时间复杂度都是O(n3).本文通过对这两种经典算法的研究与分析,提出一种求最短路径的优化算法.该算法的时间复杂度是O(e*n),在连通图中,该算法能够比Floyd算法少近50%的迭代次数,在非连通图中e<<n2,此算法的时间复杂度O(e*n)<<O(n3),比传统算法具有更明显的优势.
移動IPv6的路由尋阯是一箇最短路徑優化問題,最著名的兩種最短路徑算法是迪傑斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,這兩種算法的時間複雜度都是O(n3).本文通過對這兩種經典算法的研究與分析,提齣一種求最短路徑的優化算法.該算法的時間複雜度是O(e*n),在連通圖中,該算法能夠比Floyd算法少近50%的迭代次數,在非連通圖中e<<n2,此算法的時間複雜度O(e*n)<<O(n3),比傳統算法具有更明顯的優勢.
이동IPv6적로유심지시일개최단로경우화문제,최저명적량충최단로경산법시적걸사특랍(Dijkstra)산법화불락이덕(Floyd)산법,저량충산법적시간복잡도도시O(n3).본문통과대저량충경전산법적연구여분석,제출일충구최단로경적우화산법.해산법적시간복잡도시O(e*n),재련통도중,해산법능구비Floyd산법소근50%적질대차수,재비련통도중e<<n2,차산법적시간복잡도O(e*n)<<O(n3),비전통산법구유경명현적우세.
