采用双向搜索在多权值路网中查找较优长路径

Finding Optimal Long Paths over Multi-cost Road Networks Using Bidirectional Searches

求解最短路径是图研究中的一个经典问题。目前大多数相关研究都假设图中每条边只有一种权值。然而在实际应用中,有时候图中的边设有多种权值,求解最短路时需要综合计算多种权值,并采用用户自定义的聚合函数f将路径的多种权值映射到一个实数上,用以比较路径的长短。当f不是线性函数时,最短路的子路不一定也是最短路,于是大部分求解最短路的算法对此问题并不适用。文中提出了一种双向搜索方法,用以在多权值路网中求解最短路近似解。实验表明,本方法适用于长路径查询。与单向搜索相比,该方法有较高的运行效率。与基于Dijkstra算法的贪心算法相比,该方法有较高的准确率。

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 mul-tiple 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 pro- posed method has high efficiency. Meanwhile,compared to the greedy algorithm which is based on the Dijkstra＇s algo- rithm, the proposed method has high accuracy.