摘要
用极小代数方法求由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.
出处
《沈阳建筑工程学院学报》
1990年第4期40-44,共5页
Journal of Shenyang Archit Civil Eng Univ: Nat Sci
关键词
极小代数
最短路
有向图
系统工程
shortest path
minimal algebra: distance matrix: digraph: transportation problem
