基于L形瓦的无向双环网络直径求解算法

针对构造无向双环网络最短路径图(MDD)常用的节点遍历方式较为复杂、割裂了有向双环网络和无向双环网络之间的内在联系的问题,将有向双环网络拓扑结构映射到平面直角坐标系,在得到的L形瓦基础上,对其上的节点坐标通过简单坐标变换,得到无向双环网络MDD上对应节点坐标,进而计算无向双环网络的直径.相对于目前构造无向双环网络MDD或其等价拓扑结构普遍采用节点遍历方式而言,该算法仅增加了几次比较,就改善并提高了无向双环网络直径的求解效率.

Calculation method of bidirectional double-loop networks diameter based on L-shape tile

Node traversing method is widely used in constructing minimum distance diagram(MDD) of double-loop networks,which seperates the relationship between the bidirectional double-loop networks and the unidirectional double-loop networks.Firstly topology of unidirectional double-loop networks was reflected in Cartesian coordinates to get minimum distance diagram which was L-shape tile.Then,a method to calculate the diameter of bidirectional double-loop networks was presented based on L-shape tile to change the locations of nodes from the unidirectional region into bidirectional region in Cartesian coordinates.By using this method,the fast algorithm was presented to construct the MDD of bidirectional double-loop networks and calculate the diameter of bidirectional double-loop networks.Compared with node traversing method,this method is based on the L-shape tile and only adds a few steps to calculate,improving research of diameter of the bidirectional double-loop networks efficiently.