| 摘要: |
| 通过对固定序Bellman-Ford算法进行修正,获得了一种求解边数不大于k的最短路问题的新算法．相对于原始算法,修正后的算法通过改变点的标号过程,使得在第k次迭代后每一条路径的边数均不超过k．新算法被证明是正确的,它的计算复杂性为O(km)．实验表明,在大规模情形下,相对于修正的先进先出算法,该算法具有显著的竞争优势． |
| 关键词: 算法 Bellman-Ford算法 先进先出 固定序 最短路问题 |
| DOI：10.11918/j.issn.0367-6234.2014.11.010 |
| 分类号:TP301.6 |
| 基金项目:国家自然科学基金(71101037); 中央高校基本科研业务费专项资金(HIT.HSS.201406). |
|
| An improvement on fixed order Bellman-Ford algorithm |
|
HAN Weiyi
|
|
(School of Economic and Management, Harbin Institute of Technology, 150001 Harbin, China)
|
| Abstract: |
| In the paper, Bellman-Ford algorithm with fixed order is modified in order to solve the shortest path problem with not more than k edges. After the k-th iteration, each path must own no more than k edges by modifying the labeling process of the origin algorithm. The modified algorithm proves true and its worst-case complexity is O(km). In contrast to the modified Bellman-Ford algorithm with FIFO order, experiments show that the algorithm has the significant competitive advantage in the large-scale case. |
| Key words: algorithm Bellman-Ford algorithm FIFO order fixed order the shortest path problem |
