基于"矩阵乘法"的网络最短路径算法

• 作者: 刘丽华 周涛 邓方安 雍龙泉
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 矩阵乘法 最短路问题 约简原则 旅行商问题
• 年，卷（期）: 2009,（7）
• 所属期刊栏目: 科研通信
• 页码范围: 1594-1598
• 页数: 5页
• 分类号: TP301.6
• 字数: 3138字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2009.07.035

摘要

网络最短路径问题可以作为许多实际应用问题的模型,但传统的求解算法其迭代过程复杂.本文描述了基于矩阵乘法的最短路算法,其时间复杂度与Dijkstra算法相同.在给定的一个网络图中,在不改变网络图中的最短路的条件下,删除"多余"的结点或边,可以达到简化网络图和提高求解速度的目的,从而降低计算复杂性.最后,研究了该方法在最短路径问题和旅行商问题中的应用.实例表明,这种算法与传统的动态规划技术相比,具有运算简便、易于理解的优点.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周涛	陕西理工学院数学系	43	256	9.0	14.0
2	刘丽华	陕西理工学院数学系	28	95	4.0	8.0
3	雍龙泉	陕西理工学院数学系	111	680	12.0	21.0
4	邓方安	陕西理工学院数学系	73	398	11.0	17.0