| 具有负权最短路问题的新算法 |
| |
| 引用本文： | 张忠桢,唐小我.具有负权最短路问题的新算法[J].电子科技大学学报(社会科学版),1996(4). |
| |
| 作者姓名： | 张忠桢 唐小我 |
| |
| 作者单位： | 武汉工业大学管理工程系，电子科技大学管理学院 |
| |
| 摘 要： | 介绍具有负权最短路问题的一种新算法。这种算法以一般线性规划的投影算法以及有向图与向量之间的一种新型对应关系为基础。具有计算简便、容易理解的特声，每次迭代的计算量仅与弧数成正比。许多运筹学论著在介绍具有负权最短路算法时，假定网络中不存在负回路，这种算法可以毫无困难地处理含负回路的情形。
|
| 关 键 词： | 负权M连通片，零权M连通片，基本向量链，基本向量割集，基本向量圈 |
New Algorithms for the Shortest Path Problems with Negstive Weights |
| |
| Zhang Zhongzhen, Tang Xiaowo.New Algorithms for the Shortest Path Problems with Negstive Weights[J].Journal of University of Electronic Science and Technology of China(Social Sciences Edition),1996(4). |
| |
| Authors: | Zhang Zhongzhen Tang Xiaowo |
| |
| Abstract: | A new algorithm for the shortest path problems with negative weights are proposed in this peper.It is valid no matter whether there exist negative loops in the network.This algorithm is derived from projective algorithm for the general linear programming and a new correspondence between directed graph and vectors in which the key step is to obtain the pivoting row and column from the graph so that each iteration is completed in O(m)time. |
| |
| Keywords: | opitve loop negative loop zero loop fundamental vector chain fundamental vector cutset fundamental vector cycle |
| 本文献已被 CNKI 等数据库收录！ |
