| 负权最短路问题的新算法 |
| |
| 引用本文： | 韩伟一,王铮.负权最短路问题的新算法[J].运筹学学报,2007,11(1):111-120. |
| |
| 作者姓名： | 韩伟一 王铮 |
| |
| 作者单位： | 1. 中国科学院科技政策与管理科学研究所,北京,100080;中国科学院研究生院,北京,100039
2. 中国科学院科技政策与管理科学研究所,北京,100080;华东师范大学地理信息科学教育部重点实验室,上海,200062 |
| |
| 摘 要： | Bellman-Ford算法自1958年以来一直是负权最短路问题的公认的最好算法之一．1970年,Yen对其进行了改进,理论上可以节省一半的计算量．本文得到了一种比Bellman-Ford算法更加优越的算法．尽管在理论上新算法无法保证完全超越于Yen的改进算法,但在许多情况下需要更少的计算量．
|
| 关 键 词： | 运筹学 最短路问题 负权 Bellman-Ford算法 |
| 修稿时间： | 2006-11-08 |
An Algorithm on the Shortest Path Problem with Negative Weights |
| |
| Han Weiyi,Wang Zheng.An Algorithm on the Shortest Path Problem with Negative Weights[J].OR Transactions,2007,11(1):111-120. |
| |
| Authors: | Han Weiyi Wang Zheng |
| |
| Institution: | Institute of Policies and Management Science, CAS, Beijing 100080, China; Graduate School of the Chinese Academy of Sciences, Beijing 100039, China; Open Laboratory of Cities and Environment, Ministry of Education of China, East China Normal University, Shanghai 200062, China. |
| |
| Abstract: | It is well known that Bellman-Ford algorithm is one of best algorithms on the shortest path problem with negative weights since 1958.In 1970,Yen presented an improved algorithm which can save half of time.In the paper,a new algorithm is obtained,which is better than Bellman-Ford algorithm.Though we can't prove that the new algorithm is better than Yen's improved algorithm,it needs less time than Yen's improved algorithm in many cases. |
| |
| Keywords: | Operations research the shortest problem negative weight Bellman-Ford algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
