A Novel Solution for Simultaneously Finding the Shortest and Possible Paths in Complex Networks

Wai Mar Hlaing,
Shi-Jian Liu,
Jeng-Shyang Pan,

Abstract


A Novel graph approach named Combined Forward and Backward Heuristic Search (CFBHS) is proposed in this paper, which can be used to solve optimization problems in areas such as transportation and network routing. There are two major aspects distinct our method from the most cited ones. Firstly, though focuses on getting the shortest path in a graph when both source and destination are given, this work can also find other possible paths as outputs. Secondly, the proposed algorithm is a high-performance one, which is achieved by (1) reducing unnecessary nodes and edges to reach a target optimum based on dynamically calculated heuristic values and (2) finding the results by using the sub-division scheme instead of computing over the whole graph. Experiments are carried out for the complex road network of Yangon Region. The comparisons show that our algorithm is about 100 times faster than the bi-directional Dijkstra’s algorithm. Besides, benefit from the heuristic forward and backward search, the proposed method can achieve very low time complexity, which is similar to the A*, but A* can only produce the shortest path. By contrast, the proposed algorithm is competent for finding not only the shortest but also many possible paths in complex road networks such as undirected graph and hypergraph networks.


Citation Format:
Wai Mar Hlaing, Shi-Jian Liu, Jeng-Shyang Pan, "A Novel Solution for Simultaneously Finding the Shortest and Possible Paths in Complex Networks," Journal of Internet Technology, vol. 20, no. 6 , pp. 1693-1707, Nov. 2019.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.





Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Library and Information Center, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd. Shoufeng, Hualien 97401, Taiwan, R.O.C.
Tel: +886-3-931-7017  E-mail: jit.editorial@gmail.com