An improvement on fixed order Bellman-Ford algorithm

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.