Using Bidirectional Search to Compute Optimal Shortest Paths over Multi-weight Graphs

Computing the shortest path between two vertices in a given graph finds out vast applications. Currently most state-of-the-art research studies the shortest path computation problem in single-weight graphs, i.e., each edge in the graph has only one weight. In some applications, there are multiple weights on an edge, and those weights need to be considered when computing the shortest path. However, the sub-path property that any sub-path on a shortest path is also a shortest path, is violated in multi-weight graphs, and hence those state-of-the-arts could not be directly applied. This paper proposes a Bidirectional Best-First Search (BBFS) method with heuristic optimizations to find an optimal shortest path in multi-weight graphs. Experiments show that compared to the single search Best-First Search (BFS), BBFS has higher performance. Meanwhile, BBFS has high accuracy especially for long paths search.