基于极小代数赋权有向图最短路径求解算法

• 作者: 李彦平 王丹 谭清化 魏昆
• 来源期刊: 沈阳大学学报（自然科学版）
• 学科: 工学
• 关键词: 极小代数 赋权有向图 距离矩阵 路径规划 最短路径
• 年，卷（期）: 2015,（1）
• 所属期刊栏目: 信息与控制
• 页码范围: 25-29
• 页数: 5页
• 分类号: TP301.6
• 字数: 3920字
• 语种: 中文

摘要

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李彦平	沈阳大学辽宁省装备制造综合自动化重点实验室	37	227	8.0	13.0
5	王丹	沈阳大学辽宁省装备制造综合自动化重点实验室	56	123	6.0	8.0
6	魏昆	沈阳大学辽宁省装备制造综合自动化重点实验室	1	6	1.0	1.0
7	谭清化	沈阳大学信息工程学院	1	6	1.0	1.0