基于二叉树的有向双环网络的最短路径算法

Bintree-based shortest path algorithm of directed double-loop networks

定义了有向双环网络G(N;r,s)新的路由模型——二叉树模型,给出了0节点到二叉树模型任意一层节点的最短路径的路由策略.证明了有向双环网络的直径等于其二叉树的树高,研究了任意两节点之间的最短路径与其所在层及其相应位置的关系,给出有向双环网络任意两节点最短路径的算法.运用此算法,只需简单的算术运算和关系运算,就能快速求出任意两节点的最短路径.

A new routing modal, beetree modal, was defined for directed double-loop networks G（N; r, s）. A new routing method is presented for the shortest path between zero nodes and either node. It was proved that the diameter of directed double-loop networks equals to the height of beetree, the relationship about the shortest path for any two nodes and its position on the layer was investigated. The way to calculate the shortest path about any two nodes is proposed, by which the shortest path about any two nodes would be given easily.