用节点子树剪枝构造网络最短路径

用节点子树剪枝构造网络最短路径 Research About the Shortest Path in Network Based on the Clipping Branch Method 郭成城 1 first-author 晏蒲柳 1 夏德麟 1 武汉大学电子信息学学院,武汉,430072 武汉大学电子信息学学院,武汉,430072 College of Electronic Information, Wuhan University College of Electronic Information, Wuhan University 从网络联结国的邻接矩阵出发，提出在Ｉｎｔｅｒｎｅｔ网络环境下直接构造网络最短主树的一种方法──节点子树剪枝法．在无约束条件和有约束条件（如转接数、传输链路带宽限制情况下），给出Ｉｎｔｅｒｎｅｔ最短主树算法．该算法用于计算Ｉｎｔｅｒｎｅｔ环境下可扩展的ＩＰ路由表具有较高效率． Using graph theory the algorithm──clipping Branch in nods Subtree, to construct the shortest maintree in a scalable network environment directly was developed. The basic principle of the algorithm is explained as well as the detailed solution of it within bounds （restrains of jump number or the bandwidth of the transmission link） and not. Compared to the convential approach, the approach is a speedup with low complex of compuation. 节点子树剪枝法 路由选择 互联网 clippling branch method routing decision Internet 10.14188/j.1671-8836.2000.01.010 TP393 国家自然科学基金!（69896240）;国家863计划资助!（863－306－ZT05－2） 2000-01-01 2021-04-01 1