计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2009年
14期
84-86,103
,共4页
冷洪泽%谢政%陈挚%徐桢
冷洪澤%謝政%陳摯%徐楨
랭홍택%사정%진지%서정
根%无回路网络%最短路树形图
根%無迴路網絡%最短路樹形圖
근%무회로망락%최단로수형도
无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法.该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2)).该算法思想简便、复杂度低、易于操作.
無迴路網絡是一類重要的網絡,給齣在無迴路網絡中求解最短路樹形圖和任意頂點對間最短路的高效算法.該算法將頂點進行重新編號,結閤廣度優先探索法,從源頂點齣髮依次搜索每箇頂點的所有齣弧,併在弧的頭部進行權值變換操作,可以得到最短路樹形圖和任意頂點對間最短路,算法複雜度分彆為O(m)和O(m(n-m1/2)).該算法思想簡便、複雜度低、易于操作.
무회로망락시일류중요적망락,급출재무회로망락중구해최단로수형도화임의정점대간최단로적고효산법.해산법장정점진행중신편호,결합엄도우선탐색법,종원정점출발의차수색매개정점적소유출호,병재호적두부진행권치변환조작,가이득도최단로수형도화임의정점대간최단로,산법복잡도분별위O(m)화O(m(n-m1/2)).해산법사상간편、복잡도저、역우조작.
