用极小代数方法求解最短路径问题的进一步探讨  

FURTHER RESEAROH ON DERIVING THE SHORTEST PATH BY MINIMAL ALGEBRA METHOD

作　　者：朱德文[1] 朱禹[2] 

机构地区：[1]沈阳建筑工程学院自动化教研室 [2]沈阳建筑工程学院计算机教研室

出　　处：《沈阳建筑工程学院学报》1990年第4期40-44,共5页Journal of Shenyang Archit Civil Eng Univ: Nat Sci

摘　　要：用极小代数方法求由n个节点组成的有向连接图的最短路径公式是:A~*=sum from k=0 to n-1 (?)A^k。本文在此基础上给出了求最短路径的充要条件:A^(l+1)=A^l。举出最短运输网络实例加以说明,并和动态规划法作了比较,指出了极小代数法的优越之处。Based on the formula which is used to derive the shortest path by minimal algebra method for digraph consisting of n node, this paper presents the sufficient and necessary conditions deriving the shortest path. To explain it the paper gives an actual example of transport network and also compares with the dynamic programming method. It points out that the minimal algebra method has advantages over dynamic programming method.

关 键 词：极小代数 最短路 有向图 系统工程 

分 类 号：N94[自然科学总论—系统科学]