• May 27, 2016 News!The submission for Special Issue is officially open now!   [Click]
  • May 03, 2016 News!Vol.6, No.6 has been indexed by EI (Inspec).   [Click]
  • Mar 17, 2017 News!Vol.9, No.2 has been published with online version. 13 peer reviewed articles from 4 specific areas are published in this issue.   [Click]
General Information
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2016 Vol.8(2): 136-139 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2016.V8.1032

An Improved Algorithm of Juang’s Method by Matrix Operations for Finding the Shortest Path in Networks

Fu Sen F. Lin and Cheng-Han Lee
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).


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.

Copyright © 2008-2015. International Journal of Computer Theory and Engineering. All rights reserved.
E-mail: ijcte@vip.163.com