软件导刊
軟件導刊
연건도간
SOFT WARE GUIDE
2010年
2期
59-60
,共2页
邻接矩阵%迭代方法%拓扑排序%图的连通性%最短路径
鄰接矩陣%迭代方法%拓撲排序%圖的連通性%最短路徑
린접구진%질대방법%탁복배서%도적련통성%최단로경
全有全无的邻接矩阵法是进行最短路径计算的一种方法.矩阵迭代可以用来计算带权有向图的最短路径,迭代可以及时调整适应性,利用改进算法可以直接由D2r计算出D2r+1,最多只需「log2n-1」次.拓扑排序用于找出图中的环路,减少瓶颈.连通性用于找到图中无关节点,减少计算量.介绍了环路栓测算法,无向图中一个点和其余所有点的连通性判定,更新后的最短路径计算.
全有全無的鄰接矩陣法是進行最短路徑計算的一種方法.矩陣迭代可以用來計算帶權有嚮圖的最短路徑,迭代可以及時調整適應性,利用改進算法可以直接由D2r計算齣D2r+1,最多隻需「log2n-1」次.拓撲排序用于找齣圖中的環路,減少瓶頸.連通性用于找到圖中無關節點,減少計算量.介紹瞭環路栓測算法,無嚮圖中一箇點和其餘所有點的連通性判定,更新後的最短路徑計算.
전유전무적린접구진법시진행최단로경계산적일충방법.구진질대가이용래계산대권유향도적최단로경,질대가이급시조정괄응성,이용개진산법가이직접유D2r계산출D2r+1,최다지수「log2n-1」차.탁복배서용우조출도중적배로,감소병경.련통성용우조도도중무관절점,감소계산량.개소료배로전측산법,무향도중일개점화기여소유점적련통성판정,경신후적최단로경계산.