经典Bellman-Ford算法的改进及其实验评估

Improvement and experimental evaluation on classical Bellman-Ford algorithm

摘要:

针对以高效求解有边数限制的最短路问题,对经典Bellman-Ford算法进行了改进．借鉴划分算法的思想,通过减少距离标号的数目,得到了两个改进算法．既然已有的改进算法均不能解决有边数限制的最短路问题,因而本算法是经典Bellman-Ford算法的全新改进．相对于经典Bellman-Ford算法,改进后的算法不仅可有效地节省存储空间, 而且实验表明能显著地提高计算效率．

Abstract:

Classical Bellman-Ford algorithm is improved to solve the shortest path problem with bounded edge number efficiently. Using the experience of partitioning algorithm for reference, two improved algorithms are obtained, which can decrease the number of distance labels of vertices. Since all existing improved Bellman-Ford algorithms can’t solve the shortest path problem with bounded edge number, these two improved algorithms are entirely new. In contrast to the common version of Bellman-Ford algorithm, these two improved algorithms can save storage space efficiently, and can raise computing efficiency remarkably.