计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2014年
8期
31-34
,共4页
最短路%不含负回路网络%Floyd改进算法%迭代矩阵
最短路%不含負迴路網絡%Floyd改進算法%迭代矩陣
최단로%불함부회로망락%Floyd개진산법%질대구진
the shortest path%network without negative loop%improved Floyd algorithm%iterative matrix
目前在不含负回路的网络中,对于求解任意两节点之间最短路问题的方法有很多,Floyd算法是最经典的算法之一,但随着节点数量的增加,重复的计算量也随之增大,从而降低了计算效率。为此,文中通过迭代矩阵和下标标注法对Floyd算法进行了改进,改进后的算法既能快速地计算出网络中任意两节点之间的最短路长值,又能更直观地找出最短路径。通过具体实例分析表明,Floyd改进算法减少了重复计算,简化了路径标注方法,提高了计算效率。
目前在不含負迴路的網絡中,對于求解任意兩節點之間最短路問題的方法有很多,Floyd算法是最經典的算法之一,但隨著節點數量的增加,重複的計算量也隨之增大,從而降低瞭計算效率。為此,文中通過迭代矩陣和下標標註法對Floyd算法進行瞭改進,改進後的算法既能快速地計算齣網絡中任意兩節點之間的最短路長值,又能更直觀地找齣最短路徑。通過具體實例分析錶明,Floyd改進算法減少瞭重複計算,簡化瞭路徑標註方法,提高瞭計算效率。
목전재불함부회로적망락중,대우구해임의량절점지간최단로문제적방법유흔다,Floyd산법시최경전적산법지일,단수착절점수량적증가,중복적계산량야수지증대,종이강저료계산효솔。위차,문중통과질대구진화하표표주법대Floyd산법진행료개진,개진후적산법기능쾌속지계산출망락중임의량절점지간적최단로장치,우능경직관지조출최단로경。통과구체실례분석표명,Floyd개진산법감소료중복계산,간화료로경표주방법,제고료계산효솔。
At present,there are many algorithms for solving the shortest path between any two points in the network without negative loop. Floyd algorithm is one of the most classical algorithms. But when the number of nodes increases,the amount of repeated calculation also increases which reduces the efficiency of the algorithm. Floyd algorithm is improved in this paper by using iterative matrix and sub-script tagging method. The improved algorithm not only can calculate the shortest path weights more quickly but also find shortest paths more directly. The specific instance analysis indicates that the improved algorithm reduces the repeated calculation and simplifies the path tagging method,which lead to the improvement of the computational efficiency.
