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

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

固定序Bellman-Ford算法的一个改进

通过对固定序Bellman?Ford算法进行修正,获得了一种求解边数不大于k的最短路问题的新算法．相对于原始算法,修正后的算法通过改变点的标号过程,使得在第k次迭代后每一条路径的边数均不超过k．新算法被证明是正确的,它的计算复杂性为O（ km）．实验表明,在大规模情形下,相对于修正的先进先出算法,该算法具有显著的竞争优势．     

一类方案排斥的工程管理问题

或决策问题是由多个相互排斥的目标和约束条件形成的一类特殊的决策问题.针对0-1规划解决或决策问题建模困难,规模较大,计算效率不高等缺点,提出了一种约束条件相互排斥的或规划模型.新模型决策意义明确,建模简单,且计算效率显著,可以有效地解决方案相互排斥的工程管理问题.     

具有多条最短路径的最短路问题

尽管Dijkstra算法是解决正权单源点最短路问题公认的最好算法,但它仅能求得从源点到指定点的一条最短路径,为了给出从源点到指定点的所有最短路径,通过改进临时标号过程,得到了修正的Dijkstra算法.修正后的算法得到的不再是最短路径树,而是最短路径图.相对于原算法,修正后的算法不仅更加简便,而且应用Yen算法能够按照边数由少到多的顺序罗列出所有的最短路径.