JSW 2012 Vol.7(1): 18 ISSN: 1796217X
doi: 10.4304/jsw.7.1.1
doi: 10.4304/jsw.7.1.1
The New Algorithm for Finding the Paths based on Coding Graph
Mingfu Wang
Dept. of Software Engineering , Shenzhen Polytechnic, Shenzhen, China
Index Terms—coding graph, shortest path, critical path, Dijkstra algorithm, extending orthogonal list, time complexity.
Abstract—The most famous one for finding the shortest path is the Dijkstra, but it has some limitations. For example, when there are more than one shortest path between the source node and one special node, Dijkstra could find only one of them. Besides, the algorithm is quite complex. This article introduce a conception of coding graph, abstracting the problem of shortest paths and critical paths into the same mathematical model to describe and solve, presents a new algorithm of finding the paths. The algorithm extends first the data structure of the orthogonal list, so that the graph will be stored in the same storage space with the path searching process and result data. Codes for all nodes in the graph starting from the source node, using the rule of getting extremum in the weighing calculation and breadthfirst, When accessing recursively the adjacent nodes from the current node, reestimate the distance of neighboring node and entering edge list. if the distance of current node plus the weight of the edge to the neighboring node is less then (or greater than) the original distance of the neighboring node, then set this value as the new distance of this neighbor node, if the distance of current node plus the weight of the edge to the neighboring node is greater than (or less than) the original distance of the neighboring node, then the edge node will be deleted from the entering edge list, until all the nodes were coded and the coding graph of shortest path (or critical path) is created. For each node in the coding graph, starts searching from entry edge list recursively could get all shortest paths (or critical paths) and distances to the source node. Compared with the existing algorithms, this algorithm is simpler and more understandable, needs only 3n+5e storage unit that is much less then that of Dijkstra (which is n2+2n). The time complexity O(n+e), which is also lower than the Dijkstra O(n2).
Index Terms—coding graph, shortest path, critical path, Dijkstra algorithm, extending orthogonal list, time complexity.
[PD F]
Cite:Mingfu Wang, "The New Algorithm for Finding the Paths based on Coding Graph," Journal of Software vol. 7, no.1, pp. 18, 2014.
PREVIOUS PAPER
First page
NEXT PAPER
Match Planar Curve Based on Affine Invariant
General Information
ISSN: 1796217X (Online)
Frequency: Quarterly
EditorinChief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, CNKI, Google Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
Email: jsw@iap.org

Apr 26, 2021 News!
Vol 14, No 4 Vol 14, No 12 has been indexed by IET(Inspec) [Click]

Nov 18, 2021 News!
Papers published in JSW Vol 16, No 1 Vol 16, No 6 have been indexed by DBLP [Click]

Dec 24, 2021 News!
Vol 15, No 1 Vol 15, No 6 has been indexed by IET(Inspec) [Click]

Nov 18, 2021 News!
[CFP] 2022 the annual meeting of JSW Editorial Board, ICCSM 2022, will be held in Rome, Italy, July 2123, 2022 [Click]

Aug 01, 2023 News!