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

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.