The routing problem in the computer communication network is to determine a routing path from a source to a destination node. We are especially concerned for algorithm with the smallest communication cost. If communication cost is a length of the path, this problem will be the shorthest path problem in the connected graph.
$FLBH_N$(1,h) network is a double loop network with N nodes, such that each node has a forward link connecting to its neighbor and a backward link connecting to a node at some distance h where h is called the long hop length. In this thesis, we first characterize properties of the shorthest path and the structure of $FLBH_N$(1,h) networks. Then we divide the $FLBH_N$(1,h) networks into several levels using the properties. Second, we present a optimal shorthest path algorithm for $FLBH_N$(1,h) networks with O(log h) time and O(log h) space complexity. Finally we consider a upper bound of the maximal path length of the $FLBH_N$(1,h) network, and present a pseudo optimal path algorithm of the given network which is satisfied with a given error rate.
