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

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

Research on the Calculation and the Connectivity the Map of the Nearest Route and the Method of Topological Sorting for Adjacency Matrix

The method of all-or-nothing nearest route is one way to find the nearest route in a map.The matrix iteration method can be used to find the nearest route in a figure with directions and weights ,iteration could adjust adaptive in time,the largest number of itera- tion is[logby2^n-1] calculating D2r from D2r＋1 Topological sort is used to find the circle to reduce bottlenecks.Graph connectivity is used to find unrelate point in order to reduce the computation.This article describes the circle detection algorithm,judgement of the connectivity between a point in undirected graph and all the remaining points,the most-updated nearest route calculation.