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

韩伟一

(哈尔滨工业大学经济与管理学院，150001 哈尔滨)

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

韩伟一

(哈尔滨工业大学经济与管理学院，150001 哈尔滨)

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

算法;Bellman-Ford算法;划分算法;最短路问题

Bellman-Ford算法一般有两种表述，一种为经典的动态规划模式或经典算法［1－3］，另外一种为划分模式或划分算法(Partitioning algorithm)［4－7］.严格意义上，划分算法并不是普遍公认的经典Bellman-Ford算法，而是经过改进的Bellman-Ford算法，它把参与第i轮和第i+1轮迭代的点进行了明确划分，改进了距离标号的计算方式，能够显著提高计算效率.目前，采用先进先出策略的划分算法是解决负权最短路问题、最短路问题可行性问题的最有竞争力的算法，在算法基础上再加入门槛技术即成为解决负权最短路问题当前公认的最快算法［8－9］.尽管经典的Bellman-Ford算法在解决负权最短路问题、最短路问题可行性问题已经不具有优势，但它仍然是解决有边数限制最短路问题的最好算法［10－11］.本文将研究经典Bellman-Ford算法及其性质，并将对之进行改进，使之能更快地解决有边数限制最短路问题，同时将对改进后的算法进……