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 subdivision 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 bidirectional 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.
