一类双环网络的最优路由算法  

An Optimal Routing Algorithm for a Class of Double-loop Networks

作　　者：陈协彬[1] 

机构地区：[1]漳州师范学院数学系,漳州363000

出　　处：《漳州师范学院学报（自然科学版）》2002年第3期1-5,共5页Journal of ZhangZhou Teachers College（Natural Science)

基　　金：福建省自然科学基金资助项目(F00018).

摘　　要：设2>hn.双环网络),(hnD是如下定义的有向图:其结点集是}1,,1,0{-=nZnL,边集是}10:)(mod),(mod1{-++=ninhiiniiE.设rhrqhwhrrqhn/)/()1(,11,+-=-+=又设这里.本文提出了),(hnD中源结点到目的结点的最短路径算法,该算法至多只要两次算术运算和一次比较,并且除了q,h,r和w外,各结点不必预先存储网络中别的信息.Let 2>hn. The double-loop network D(n, h) is a directed graph with its node set }1,,1,0{-=nZnL and edge set :)(mod),mod1{nhiiniiE++=( }10-ni. Let rqhn+=where 11-hr, and rhrqhw/)/()1(+-=. In this paper, a routing algorithm is proposed for finding a shortest path from a source node to a destination node in D(n, h). The algorithm consists of at most two arithmetic operations and one comparison, and no other information about D(n, h) is stored beforehand in the source node except for q, h, r and w.

关 键 词：最优路由算法 双环网络 有向图 结点集 边集 最短路径算法 源结点 目的结点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O157.5[自动化与计算机技术—计算机科学与技术]