| 摘要: |
| 针对以高效求解有边数限制的最短路问题,对经典Bellman-Ford算法进行了改进．借鉴划分算法的思想,通过减少距离标号的数目,得到了两个改进算法．既然已有的改进算法均不能解决有边数限制的最短路问题,因而本算法是经典Bellman-Ford算法的全新改进．相对于经典Bellman-Ford算法,改进后的算法不仅可有效地节省存储空间, 而且实验表明能显著地提高计算效率． |
| 关键词: 算法 Bellman-Ford算法 划分算法 最短路问题 |
| DOI：10.11918/j.issn.0367-6234.2012.07.014 |
| 分类号:TP3016 |
| 基金项目:国家自然科学基金资助项目(70672063); 哈尔滨工业大学青年优秀基金资助项目(2009036). |
|
| Improvement and experimental evaluation on classical Bellman-Ford algorithm |
|
HAN Wei-yi
|
|
School of Economic and Management, Harbin Institute of Technology, 150001 Harbin, China
|
| 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. |
| Key words: algorithm Bellman-Ford algorithm partitioning algorithm the shortest path problem |
