| 最短路问题的Auction算法在无圈网络中的改进 |
| |
| 引用本文： | 张青华,杨骅飞.最短路问题的Auction算法在无圈网络中的改进[J].上海理工大学学报(社会科学版),2003,25(3):251-254. |
| |
| 作者姓名： | 张青华 杨骅飞 |
| |
| 作者单位： | 北京理工大学理学院，北京理工大学理学院 北京 100081，北京 100081 |
| |
| 摘 要： | 提出了Auction算法在无圈网络中的一种改进．在改进的新算法中，采取了新的推进(extension)方式，从而成功地降低了算法的复杂性．改进后算法的复杂性为O(m)，此处m是图的弧数．
|
| 关 键 词： | 最短路 Auction算法 对偶算法 |
Improvement of auction algorithm for shortest path problems in acyclic networks |
| |
| ZHANG Qing-hu,YANG Hua-fei.Improvement of auction algorithm for shortest path problems in acyclic networks[J].Journal of University of Shanghai For Science and Technilogy(Social Science),2003,25(3):251-254. |
| |
| Authors: | ZHANG Qing-hu YANG Hua-fei |
| |
| Abstract: | Auction algorithm for shortest path problems was firstly proposed by Prof Bertsekas in 1991. In the paper, a new variant in acyclic networks is proposed, in which a new extension method is adopted, and the complexity is then reduced to O(m), where m is the number of edges. |
| |
| Keywords: | shortest path Auction algorithm dual algorithm |
|
| 点击此处可从《上海理工大学学报(社会科学版)》浏览原始摘要信息 |
| 点击此处可从《上海理工大学学报(社会科学版)》下载免费的PDF全文 |
