用于道路网的最短路径搜索方法及装置

摘要

本发明公开了一种用于道路网的最短路径搜索方法及装置，其中，方法包括以下步骤：将道路网分割为多个子网络；生成树状结构道路网络；计算同一层的子网络的边界节点之间的最短路径；输入查询点和目标点；根据最短路径通过动态规划算法得到查询点和目标点之间的初始最短路径；对初始最短路径进行补充以获取查询点和目标点之间完整的最短路径。本发明实施例的方法通过将道路网分割为多个子网络以生成树状结构道路网络，并且计算同一层的子网络的边界节点之间的最短距离，从而当输入查询点和目标点时，实现快速得到查询点和目标点之间最短路径，不但效率高，而且很好地满足实时性要求。

主权项

一种用于道路网的最短路径搜索方法，其特征在于，包括以下步骤：将道路网分割为多个子网络；根据所述多个子网络生成树状结构道路网络，其中，所述树状结构道路网络中每个节点为一个子网络；计算所述树状结构道路网络中同一层的子网络的边界节点之间的最短路径；输入查询点和目标点；根据所述树状结构道路网络中同一层的子网络的边界节点之间的最短路径通过动态规划算法得到所述查询点和目标点之间的初始最短路径；以及对所述初始最短路径进行补充以获取所述查询点和目标点之间完整的最短路径。