全局最短路径计算和图的连通性及拓扑排序在邻接矩阵的方法

• 作者: 赵孜泷
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: 邻接矩阵 迭代方法 拓扑排序 图的连通性 最短路径
• 年，卷（期）: 2010,（2）
• 页码范围: 59-60
• 分类号: TP312
• 字数: 1982字
• 语种: 中文

摘要

全有全无的邻接矩阵法是进行最短路径计算的一种方法.矩阵迭代可以用来计算带权有向图的最短路径,迭代可以及时调整适应性,利用改进算法可以直接由D2r计算出D2r+1,最多只需「log2n-1」次.拓扑排序用于找出图中的环路,减少瓶颈.连通性用于找到图中无关节点,减少计算量.介绍了环路栓测算法,无向图中一个点和其余所有点的连通性判定,更新后的最短路径计算.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵孜泷	武汉科技大学城市学院信息学部	1	2	1.0	1.0