Volume 7 Number 1 (Jan. 2012)
Home > Archive > 2012 > Volume 7 Number 1 (Jan. 2012) >
JSW 2012 Vol.7(1): 1-8 ISSN: 1796-217X
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

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, re-estimate 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. 1-8, 2014.

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Nov 18, 2019 News!

    Papers published in JSW Vol 14, No 1- Vol 14 No 10 have been indexed by DBLP     [Click]

  • Jun 25, 2019 News!

    Vol.13, No.9 has been indexed by EI (Inspec).   [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Jul 10, 2019 News!

    Vol 14, No.8 has been published with online version 4 original aritcles from 2 countries are published in this issue.    [Click]

  • Nov 18, 2019 News!

    Vol 14, No 11 has been published with online version 4 original aritcles from 4 countries are published in this issue     [Click]