运筹与管理
運籌與管理
운주여관리
Operations Research and Management Science
2015年
4期
111-115
,共5页
运筹学%固定序改进算法%最短路序%拓扑序Bellman-Ford算法
運籌學%固定序改進算法%最短路序%拓撲序Bellman-Ford算法
운주학%고정서개진산법%최단로서%탁복서Bellman-Ford산법
operations research%improved fixed order algorithm%the shortest path order%topological order%bellman-ford algorithm
固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势，本文通过预先订制参与迭代的点的计算顺序，对该算法进行了改进。实验表明，在稀疏图上，改进后的算法相对于原算法计算效率提高了近50％，并能够与国际流行的先进先出算法相媲美。本文的工作表明，固定序算法不仅在大规模稠密图上具有明显的优势，而且在稀疏图上也具有很强的竞争力。
固定序算法是Bellman-Ford算法的一種基本改進算法。為瞭改變固定序算法在稀疏圖上的劣勢，本文通過預先訂製參與迭代的點的計算順序，對該算法進行瞭改進。實驗錶明，在稀疏圖上，改進後的算法相對于原算法計算效率提高瞭近50％，併能夠與國際流行的先進先齣算法相媲美。本文的工作錶明，固定序算法不僅在大規模稠密圖上具有明顯的優勢，而且在稀疏圖上也具有很彊的競爭力。
고정서산법시Bellman-Ford산법적일충기본개진산법。위료개변고정서산법재희소도상적열세，본문통과예선정제삼여질대적점적계산순서，대해산법진행료개진。실험표명，재희소도상，개진후적산법상대우원산법계산효솔제고료근50％，병능구여국제류행적선진선출산법상비미。본문적공작표명，고정서산법불부재대규모주밀도상구유명현적우세，이차재희소도상야구유흔강적경쟁력。
The fixed order algorithm is one of basic improved algorithms on the classic Bellman-Ford algorithm.In view of its inferiority in the sparse directed graph, the algorithm is improved by presenting the computational order of vertices in advance.The experiments show that the improved algorithm is faster than the original one by 50%in the sparse directed graph approximately.Moreover, it is compared with the FIFO algorithm, which is the most attractive basic improved algorithm of Bellman-Ford algorithm at present.It means that the fixed order algo-rithm is very competitive in both the large-scale dense directed graph and the sparse directed graph.
