Affiliations: Key Lab of Intelligent Computing & Signal
Processing at Anhui University, Anhui University, Hefei, People's Republic of
China, 230039, China. [email protected]
Note: [] Address for correspondence: Key Lab of Intelligent Computing & Signal Processing at Anhui University, Ministry of
Education, Anhui University, Hefei, Peoples Republic of China, 230039
Abstract: The optimal path finding problem in weighted edge networks is an old
and interesting one in many fields. There were many well-known algorithms to
deal with that issue. But they were confronted with the high computational
complexity while the network becoming larger. We present a hierarchical
quotient space model based algorithm that reduces the computational complexity.
The basic idea is the following. The nodes of a given network are partitioned
with respect to the weights of their adjacent edges. We construct a variety of
coarser versions of the given network with new nodes corresponding to the
blocks of partitions at various levels of granularity. They are called the
quotient spaces (networks) of the original network. The construction of the
(sub- )optimal path is then done incrementally, throughout the hierarchy of
quotient networks. Since each version of the network is much simpler than the
original one, especially of the coarsest spaces, the computational complexity
is reduced. In this paper, we present the basic principles of the algorithm and
its experimental comparison to other well-known algorithms.
