| 无回路网络中的最小费用流算法 |
| |
| 引用本文： | 黄伟,陈维维,房元平. 无回路网络中的最小费用流算法[J]. 微计算机应用, 2010, 31(12) |
| |
| 作者姓名： | 黄伟 陈维维 房元平 |
| |
| 作者单位： | 暨南大学信息科学技术学院; |
| |
| 摘 要： | 针对无回路网络的特殊性,利用广探法的思想,提出了无回路网络最短路的有效算法,并在此基础之上提出了最小费用流的有效算法.其算法的复杂性分别为o(m)和o(mvo),相比拓扑排序法和最小费用路算法,本文提出的算法更为简练、易懂且复杂性低.
|
| 关 键 词： | 无回路网络 最短路 最小费用流 |
Efficient Algorithm for the Minimum Cost Flow in DAG |
| |
| HUANG Wei,CHEN Weiwei,FANG Yuanping. Efficient Algorithm for the Minimum Cost Flow in DAG[J]. Microcomputer Applications, 2010, 31(12) |
| |
| Authors: | HUANG Wei CHEN Weiwei FANG Yuanping |
| |
| Affiliation: | HUANG Wei,CHEN Weiwei,FANG Yuanping(College of Information Science and Technology,Jinan University,Guangzhou,510632,China) |
| |
| Abstract: | According to the Special nature of the DAG,A high-efficient algorithm to seek the shortest path in DAG is presented by the idea of breadth first search,on this basis,we Propose an algorithm for the minimum cost flow in DAG.The Complexity of the two Algorithms are respectively in time o(m) and o(mvo).Correlative analysis and instances indicate that this algorithm is superior to other current algorithms in respect of computing complexity,operation,etc. |
| |
| Keywords: | DGA the shortest path the minimum cost flow |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
