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

摘要

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