关键词: 最短路径,多权值图,双向搜索,长路径 中图法分类号TP301.6文献标识码A

Abstract: Finding the shortest path is a classic problem in graph studies．Current researches mostly suppose that each edge in the graph has a single cost．However,in some cases,each edge might have multiple costs,which all have to be taken into consideration when computing the shortest path．A user defined aggregate function f is used to map the multiple costs of a path to a real number,from which the lengths of two paths can be compared．When f is not linear,the sub path of a shortest path is not necessarily a shortest path,and thus,most state-of-the art solutions can not be applied to this problem．This paper proposed a bidirectional search method that can find the optimal shortest paths．Experiments show that the proposed method is suitable for the long paths queries．Compared to the single directional search,the proposed method has high efficiency．Meanwhile,compared to the greedy algorithm which is based on the Dijkstra’s algorithm,the proposed method has high accuracy．

Key words: Shortest path,Multi-cost graph,Bidirectional search,Long path