General Information
    • ISSN: 1793-8201 (Print), 2972-4511 (Online)
    • Abbreviated Title: Int. J. Comput. Theory Eng.
    • Frequency: Quarterly
    • DOI: 10.7763/IJCTE
    • Editor-in-Chief: Prof. Mehmet Sahinoglu
    • Associate Editor-in-Chief: Assoc. Prof. Alberto Arteta, Assoc. Prof. Engin Maşazade
    • Managing Editor: Ms. Mia Hu
    • Abstracting/Indexing: Scopus (Since 2022), INSPEC (IET), CNKI,  Google Scholar, EBSCO, etc.
    • Average Days from Submission to Acceptance: 192 days
    • E-mail: ijcte@iacsitp.com
    • Journal Metrics:

Editor-in-chief
Prof. Mehmet Sahinoglu
Computer Science Department, Troy University, USA
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).

[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.


Copyright © 2008-2024. International Association of Computer Science and Information Technology. All rights reserved.