Abstract—A new algorithm of finding the shortest path in networks by matrix operations and linear combinations of paths is presented in this paper. In 2007, a novel method for solving the shortest path problem was proposed by Juang. Juang’s algorithm is based on the concept of Kruskal’s algorithm associated with RREF processing (Gauss-Jordan elimination) and a matrix transformation. However, Juang’s scheme only can work in some special well-connected networks. We therefore design a new approach by following the basic steps of Juang’s algorithm and adding the linear combination of fundamental cut-sets. The presented algorithm (called JLL-SP algorithm) can overcome the failure cases of Juang’s method and work correctly and efficiently for wider range of networks. The experimental results verified that the JLL-SP algorithm performs well in most unilaterally connected digraphs.
Index Terms—Connected digraphs, linear transformation, linear combination, RREF matrix, shortest path.
The authors are with the Department of Computer Science and Engineering at National Taiwan Ocean University, Keelung, 20224 Taiwan (e-mail: fslin@ntou.edu.tw, wilson_1886@hotmail.com).
[PDF]
Cite:Fu Sen F. Lin and Cheng-Han Lee, "An Improved Algorithm of Juang’s Method by Matrix Operations for Finding the Shortest Path in Networks," International Journal of Computer Theory and Engineering vol. 8, no. 2, pp. 136-139, 2016.