一种基于最短路径和路径枚举的道路网选址方法和系统与流程

1.本发明属于图计算和大数据技术领域，更具体地，涉及一种基于最短路径和路径枚举的道路网选址方法和系统。


背景技术：

2.道路网选址是指在给定的道路网络中选择合适的位置建设服务设施，以满足用户的需求和优化资源利用。现实生活中位置选择需求应用的不断增加，基于道路网选址服务变得越来越重要，其应用已覆盖社交、旅行、综合生活服务等多个领域，用户已经习惯并充分使用“道路网选址服务+手机应用”带来的便利，比如，现在生活中常用的高德地图、美团、滴滴出行等。无论从终端用户还是地图运营商角度来说，基于道路网选址已然成为社会生活中一项不可或缺的基础服务。因此，寻找一种满足用户需求的多样性且准确有效的道路网选址方法是具有很大的现实意义。
3.由于现有道路网选址方法的度量方式过于单一，针对道路网选址方法主要是基于最短路径方法或基于路径枚举方法。第一种方法是基于迪杰斯特拉(dijkstra)算法实现的，该算法定义一个顶点集合s，其用于存储已经确定了最短路径的顶点，以及一个距离集合d，其用于存储从起点到每个顶点的最短距离。算法开始时，将起点加入集合s中，并将其距离设置为0，然后，算法通过不断地向集合s中加入距离最短的顶点，并更新从起点到其他节点的距离，直到集合s包含了所有顶点或者找到了终点为止；第二种方法是基于深度优先搜索(depth first search，简称dfs)实现的，其基本思想是从一个起点开始，依次沿着一个方向走到底，直到到达终点或者不能继续往下走为止，路径枚举中，深度优先搜索可以用来寻找从一个起点开始的所有路径。
4.然而，上述两种方法均存在一些不可忽略的缺陷：第一，上述基于dijkstra算法的道路网选址方法是通过计算两个顶点之间的最短路径是基于dijkstra算法实现的，它是一种基于局部最优解来构建全局最优解的贪心算法，由于搜索过程中只能根据已知的信息进行决策，不能提前预测终点的位置，具有盲目性，导致搜索效率低；第二，上述基于dfs的道路网选址方法是通过枚举所有路径进行地址选择，由于没有设置适当的路径阈值，用户可能会被大量路径淹没，并且枚举所有路径是很耗时的，甚至有些路径是无用的，这种方法性价比低，搜索速度慢。


技术实现要素：

5.针对现有技术的以上缺陷或改进需求，本发明提供了一种基于最短路径和路径枚举的道路网选址方法。其目的在于，解决现有基于dijkstra算法的道路网选址方法由于搜索过程中只能根据已知的信息进行决策，不能提前预测终点的位置，具有盲目性，导致查询效率低的技术问题；以及现有基于dfs的道路网选址方法由于没有设置适当的路径距离约束，用户可能会被大量路径淹没，并且枚举所有路径耗时、以及有些路径无用，导致效率很低，搜索速度慢的技术问题。
6.为实现上述目的，按照本发明的一个方面，提供了一种基于最短路径和路径枚举的道路网选址方法，包括以下步骤：
7.(1)读取真实道路网络数据集，提取其中的顶点和边数据，并根据提取的顶点和边数据建立无向有权图；
8.(2)使用函数readgraph()对步骤(1)得到的无向有权图进行读取处理，以得到起点集合；
9.(3)使用函数readgraph()对步骤(1)得到的无向有权图进行读取处理，以得到终点集合；
10.(4)使用深度优先搜索dfs方法对步骤(2)得到的起点集合和步骤(3)得到的终点集合进行处理，以得到所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径。
11.(5)对步骤(4)得到的每个起点到每个终点之间、且处于预设的路径阈值d范围内的所有路径进行降序排序处理，以得到每个起点到所有终点中的路径数量最大值及其对应的终点，该终点即道路网选址中所要选择的最相关点。
12.优选地，步骤(1)首先是从snap数据集官网上获取真实道路网络数据集，然后，利用函数read_vertex()从该真实道路网络数据集中提取顶点文件，随后，从顶点文件中获取所有顶点的数据，每条顶点数据包括顶点编号和其对应的经纬度，然后，将每个顶点的经纬度存储在一个顶点集合中；其后，利用函数read_edge()从该真实道路网络数据集中提取边文件，随后，从边文件中获取所有边的数据，每条数据包括边起点和终点的编号，然后，将每条边起点和终点的编号存储在一个边集合中；其后，依次从边集合中取出每条边起点和终点的编号，根据起点和终点的编号从顶点集合中取出对应的经纬度，然后，根据这两个顶点的经纬度计算出边的权重；随后，将计算得到的任意两个顶点之间的权重添加到边集合中；最后，根据边集合里存储的边数据与其对应的权重建立一个无向有权图。
13.优选地，边的权重是根据如下算式计算得到的：
[0014][0015]
其中r表示地球半径；分别表示顶点1和顶点2的纬度；λ1、λ2分别表示顶点1和顶点2的经度。
[0016]
优选地，步骤(2)包括以下子步骤：
[0017]
(2-1)设置计数器i＝0；
[0018]
(2-2)判断计数器i是否小于等于迭代总数m，如果是则进入步骤(2-3)，否则过程结束；
[0019]
(2-3)对无向有权图进行读取操作，以得到无向有权图的所有顶点，利用函数rand()随机生成一个起点，随后，将生成的起点插入到起点集合，该起点集合初始为空；
[0020]
优选地，步骤(3)包括以下子步骤：
[0021]
(3-1)设置计数器j＝0；
[0022]
(3-2)判断计数器j是否小于等于迭代总数n，如果是则进入步骤(3-3)，否则过程结束。
[0023]
(3-3)对无向有权图进行读取操作，以得到无向有权图的所有顶点，利用函数rand()随机生成一个终点，随后，进入步骤(3-4)；
[0024]
(3-4)设置计数器k＝0；
[0025]
(3-5)判断计数器k是否小于等于起点集合的大小m，如果是，则进入步骤(3-6)，否则设置j＝j+1，并返回步骤(3-2)；
[0026]
(3-6)利用dijkstra算法计算终点集合中的第j个终点到起点集合中的第k个起点的最短距离；
[0027]
(3-7)判断得到第j个终点到第k个起点的最短距离是否小于或等于预设的路径阈值d，如果是，则进入步骤(3-8)，否则设置k＝k+1，并返回步骤(3-5)。
[0028]
(3-8)将第j个终点插入到终点集合，该终点集合初始为空。
[0029]
优选地，步骤(4)包括以下子步骤：
[0030]
(4-1)设置计数器a＝0；
[0031]
(4-2)判断计数器a是否小于等于起点集合的大小m，如果是则进入步骤(4-3)，否则过程结束；
[0032]
(4-3)设置计数器b＝0；
[0033]
(4-4)判断计数器b是否小于等于终点集合的大小n，如果是则进入步骤(4-5)，否则设置a＝a+1，并返回步骤(4-2)；
[0034]
(4-5)使用dijkstra算法计算无向有权图中除了第b个终点以外的每个顶点到终点b的最短距离，并将计算得到的多个最短距离存储在一个数组sd中，该数组sd初始为空；
[0035]
(4-6)设置计数器c＝0(其用于记录每个起点到每个终点满足预设的路径阈值d范围内的路径数量)，初始化集合visited为空(该集合用于存储已搜索过的顶点)，初始化已搜索的路径距离dis为零，并将起点集合中的第a个起点作为当前搜索顶点v；
[0036]
(4-7)判断当前搜索顶点v是否等于终点集合中的第b个终点，如果是，则设置c＝c+1，然后进入步骤(4-13)，否则进入步骤(4-8)；
[0037]
(4-8)将当前搜索顶点v插入到集合visited中，并进入步骤(4-9)；
[0038]
(4-9)获取当前搜索顶点v的邻居顶点w，并进入步骤(4-10)；
[0039]
(4-10)判断邻居顶点w是否位于集合visited中，如果是，则表示该顶点已访问过，不必重新搜索避免重复，并返回步骤(4-9)，否则进入步骤(4-11)；
[0040]
(4-11)判断邻居顶点w是否同时满足以下两个条件：
①
已搜索的路径距离dis(dis＝dis+邻居顶点w到当前搜索顶点v之间的距离)是否小于等于预设的路径阈值d；
②
由步骤(4-5)计算得到的顶点w到终点b的最短距离sd[w]+已搜索的路径距离dis是否小于等于预设的路径阈值d，如果是，则进入步骤(4-12)，否则对邻居顶点w进行剪枝操作，停止访问邻居顶点w的所有邻居顶点；
[0041]
(4-12)将第a个起点的邻居顶点w作为当前搜索顶点v，并返回步骤(4-7)；
[0042]
(4-13)将集合visited中的所有顶点清空，并返回起点集合中的第a个起点到终点集合中的第个终点b的路径数量c。
[0043]
按照本发明的另一方面，提供了一种基于最短路径和路径枚举的道路网选址系统，包括：
[0044]
第一模块，用于读取真实道路网络数据集，提取其中的顶点和边数据，并根据提取
的顶点和边数据建立无向有权图；
[0045]
第二模块，用于使用函数readgraph()对第一模块得到的无向有权图进行读取处理，以得到起点集合；
[0046]
第三模块，用于使用函数readgraph()对第一模块得到的无向有权图进行读取处理，以得到终点集合；
[0047]
第四模块，用于使用深度优先搜索dfs方法对第二模块得到的起点集合和第三模块得到的终点集合进行处理，以得到所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径。
[0048]
第五模块，用于对第四模块得到的每个起点到每个终点之间、且处于预设的路径阈值d范围内的所有路径进行降序排序处理，以得到每个起点到所有终点中的路径数量最大值及其对应的终点，该终点即道路网选址中所要选择的最相关点。
[0049]
总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：
[0050]
(1)由于本发明采用了步骤(4-5)，预计算终点到除终点之外的其他顶点最短距离，并将其最短距离存储在一个数组中，这样搜索过程中能够根据数组存储的最短距离提前预测终点位置，避免盲目搜索，因此能够解决上述第一种方法存在的搜索效率低的技术问题；
[0051]
(2)由于本发明采用了步骤(3-6)、(4-11)，预先设置适当的路径阈值d，判断当前路径距离是否满足预设的路径阈值d，根据这个条件作为路径枚举过程中的剪枝条件，能够有效地、尽可能地避免枚举一些不满足路径阈值约束的路径，因此能够解决上述第二种方法存在的性价比低、搜索速度慢的技术问题；
[0052]
(3)本发明方法的实现简单有效；
[0053]
(4)本发明方法的实际应用领域广泛。
附图说明
[0054]
图1是本发明基于最短路径和路径枚举的道路网选址方法的流程示意图；
[0055]
图2是道路网选址请求的一个示例图；
[0056]
图3是本发明方法得到的算法运行时间折线图。
具体实施方式
[0057]
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
[0058]
本发明的基本思路在于，从四个方面改进道路网选址的方法，首先获取真实网络数据集并建立无向有权图；其次，利用函数readgraph()读取无向有权图，将rand()函数随机生成的起点和终点分别存入起点和终点集合；然后，使用深度优先搜索(dfs)方法来寻找所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径；最后，根据每个起点到每个终点的路径数量依次降序排序，选取每个起点到所有终点中的路径数量最大值及
其对应的终点，该终点即道路网选址中所要选择的最相关点。
[0059]
如图1所示，本发明提供了一种基于最短路径和路径枚举的道路网选址方法，包括以下步骤：
[0060]
(1)读取真实道路网络数据集，提取其中的顶点和边数据，并根据提取的顶点和边数据建立无向有权图；
[0061]
具体而言，本步骤首先从snap数据集官网上获取真实道路网络数据集，然后，利用函数read_vertex()从该真实道路网络数据集中提取顶点文件，随后，从顶点文件中获取所有顶点的数据，每条顶点数据包括顶点编号和其对应的经纬度，然后，将每个顶点的经纬度存储在一个顶点集合中；其后，利用函数read_edge()从该真实道路网络数据集中提取边文件，随后，从边文件中获取所有边的数据，每条数据包括边起点和终点的编号，然后，将每条边起点和终点的编号存储在一个边集合中；其后，依次从边集合中取出每条边起点和终点的编号，根据起点和终点的编号从顶点集合中取出对应的经纬度，然后，根据这两个顶点(顶点1和顶点2)的经纬度计算出边的权重(weight)。边的权重是根据如下算式计算得到的：
[0062][0063]
该算式是由haversine公式推导出来的，其中r表示地球半径；分别表示顶点1和顶点2的纬度；λ1、λ2分别表示顶点1和顶点2的经度。
[0064]
随后，将计算得到的任意两个顶点之间的权重添加到边集合中；最后，根据边集合里存储的边数据与其对应的权重建立一个无向有权图。
[0065]
(2)使用函数readgraph()对步骤(1)得到的无向有权图进行读取处理，以得到起点集合；
[0066]
步骤(2)包括以下子步骤：
[0067]
(2-1)设置计数器i＝0；
[0068]
(2-2)判断计数器i是否小于等于迭代总数m，如果是则进入步骤(2-3)，否则过程结束；
[0069]
在本实施方式中，迭代总数m取值范围是0到10之间，优选为5；
[0070]
(2-3)对无向有权图进行读取操作，以得到无向有权图的所有顶点，利用函数rand()随机生成一个起点，随后，将生成的起点插入到起点集合(其初始为空)；
[0071]
(3)使用函数readgraph()对步骤(1)得到的无向有权图进行读取处理，以得到终点集合；
[0072]
步骤(3)包括以下子步骤：
[0073]
(3-1)设置计数器j＝0；
[0074]
(3-2)判断计数器j是否小于等于迭代总数n，如果是则进入步骤(3-3)，否则过程结束；
[0075]
在本实施方式，迭代总数n取值范围是0到1000之间，优选为500；
[0076]
(3-3)对无向有权图进行读取操作，以得到无向有权图的所有顶点，利用函数rand()随机生成一个终点，随后，进入步骤(3-4)；
[0077]
(3-4)设置计数器k＝0；
[0078]
(3-5)判断计数器k是否小于等于起点集合的大小m，如果是，则进入步骤(3-6)，否则设置j＝j+1，并返回步骤(3-2)；
[0079]
(3-6)利用迪杰斯特拉(dijkstra)算法计算终点集合中的第j个终点到起点集合中的第k个起点的最短距离；
[0080]
(3-7)判断得到第j个终点到第k个起点的最短距离是否小于或等于预设的路径阈值d，如果是，则进入步骤(3-8)，否则设置k＝k+1，并返回步骤(3-5)。
[0081]
(3-8)将第j个终点插入到终点集合(其初始为空)。
[0082]
具体而言，路径阈值d取值范围是3km到7km之间，优选为5km；
[0083]
本步骤的优点在于，通过dijkstra算法预计算终点到起点的最短距离，并选取其最短距离满足预设的路径阈值d范围内的终点，为之后的路径搜索提供有效终点，因为如果终点到起点的最短距离大于预设的路径阈值d，那么搜索该终点是毫无意义的。
[0084]
(4)使用深度优先搜索(dfs)方法对步骤(2)得到的起点集合和步骤(3)得到的终点集合进行处理，以得到所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径；
[0085]
如图2所示，其表示出道路网中选址请求的一个示例，在图2中蓝色顶点代表起点集合s＝{v0,v4}，绿色顶点代表终点集合t＝{v7,v
11
,v
12
}，预设的路径阈值d＝5km，通过使用dfs方法得到起点v0到终点v7,v
11
,v
12
满足5km范围内的路径数量分别为2、3和0，起点v4到终点v7,v
11
,v
12
满足5km范围内的路径数量分别为2、4和3。
[0086]
步骤(4)包括以下子步骤：
[0087]
(4-1)设置计数器a＝0；
[0088]
(4-2)判断计数器a是否小于等于起点集合的大小m，如果是则进入步骤(4-3)，否则过程结束；
[0089]
(4-3)设置计数器b＝0；
[0090]
(4-4)判断计数器b是否小于等于终点集合的大小n，如果是则进入步骤(4-5)，否则设置a＝a+1，并返回步骤(4-2)；
[0091]
(4-5)使用dijkstra算法计算无向有权图中除了第b个终点以外的每个顶点到终点b的最短距离，并将计算得到的多个最短距离存储在一个数组sd中(该数组sd初始为空)；
[0092]
本步骤的优点在于，通过dijkstra算法预计算除了第b个终点以外的所有顶点到终点b的最短距离，为后续步骤(4-11)判断路径距离是否满足预设的路径阈值d提供剪枝条件。
[0093]
(4-6)设置计数器c＝0(其用于记录每个起点到每个终点满足预设的路径阈值d范围内的路径数量)，初始化集合visited为空(该集合用于存储已搜索过的顶点)，初始化已搜索的路径距离dis为零，并将起点集合中的第a个起点作为当前搜索顶点v；
[0094]
(4-7)判断当前搜索顶点v是否等于终点集合中的第b个终点，如果是，则设置c＝c+1，然后进入步骤(4-13)，否则进入步骤(4-8)；
[0095]
(4-8)将当前搜索顶点v插入到集合visited中，并进入步骤(4-9)；
[0096]
本步骤的优点在于，利用一个数组存储已访问过的顶点，这样保证其搜索过程不会重复访问已搜索过的顶点，以避免循环访问，降低查询效率。
[0097]
(4-9)获取当前搜索顶点v的邻居顶点w，并进入步骤(4-10)；
[0098]
(4-10)判断邻居顶点w是否位于集合visited中，如果是，则表示该顶点已访问过，不必重新搜索避免重复，并返回步骤(4-9)，否则进入步骤(4-11)；
[0099]
(4-11)判断邻居顶点w是否同时满足以下两个条件：
①
已搜索的路径距离dis(dis＝dis+邻居顶点w到当前搜索顶点v之间的距离)是否小于等于预设的路径阈值d；
②
由步骤(4-5)计算得到的顶点w到终点b的最短距离sd[w]+已搜索的路径距离dis是否小于等于预设的路径阈值d，如果是，则进入步骤(4-12)，否则对邻居顶点w进行剪枝操作，停止访问邻居顶点w的所有邻居顶点；
[0100]
(4-12)将第a个起点的邻居顶点w作为当前搜索顶点v，并返回步骤(4-7)；
[0101]
(4-13)将集合visited中的所有顶点清空，并返回起点集合中的第a个起点到终点集合中的第个终点b的路径数量c。
[0102]
(5)对步骤(4)得到的每个起点到每个终点之间、且处于预设的路径阈值d范围内的所有路径进行降序排序处理，以得到每个起点到所有终点中的路径数量最大值及其对应的终点，该终点即道路网选址中所要选择的最相关点。
[0103]
如图2所示，步骤(4)使用dfs方法得到起点v0到终点v7,v
11
,v
12
满足5km范围内的路径数量分别为2、3和0，对路径数量进行排序，选取路径数量最大对应的终点v
11
作为起点v0的最相关点；起点v4到终点v7,v
11
,v
12
满足5km范围内的路径数量分别为2、4和3，对路径数量进行排序，选取路径数量最大对应的终点v
11
作为起点v4的最相关点
[0104]
具体而言，本步骤定义两个变量max和result，分别用于存储最大路径数量和对应的终点编号，初始化值均为0。对每次调用步骤(4)得到的路径数量c与max变量值进行比较大小处理，如果路径数量c大于变量max，则将c的值赋给变量max，以得到路径数量最大值，同时将当前遍历的终点编号赋给result，对变量max和result进行输出处理，以得到每个起点到终点的最大路径数量和每个起点的最相关点，因为两个顶点之间路径数量越多，说明两点之间的相关性越强。
[0105]
模拟测试结果
[0106]
以下描述本发明的测试环境、测试数据和测试结果：
[0107]
测试环境是c++，在操作系统windows11、处理器的主频为2.30ghz的intel(r)core(tm)i7-12700h处理器16gb内存的电脑上进行实验测试。
[0108]
测试数据是真实道路网络图数据，包括106600个顶点和130091条边。
[0109]
测试结果是图3给出了测试环境下获得的基于最短路径和路径枚举算法运行时间折线图，横坐标代表预设的路径阈值d的值，纵坐标代表每更改一次预设的路径阈值d所需要运行的时间，从图2中可以看出，算法的运行时间随着预设的路径阈值d不断增长。算法运行时间在路径距离约束d＝5000米前，几乎变化不大，在d＝5000米后，算法运行时间呈线性增长。
[0110]
本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种基于最短路径和路径枚举的道路网选址方法，其特征在于，包括以下步骤：(1)读取真实道路网络数据集，提取其中的顶点和边数据，并根据提取的顶点和边数据建立无向有权图；(2)使用函数readgraph()对步骤(1)得到的无向有权图进行读取处理，以得到起点集合；(3)使用函数readgraph()对步骤(1)得到的无向有权图进行读取处理，以得到终点集合；(4)使用深度优先搜索dfs方法对步骤(2)得到的起点集合和步骤(3)得到的终点集合进行处理，以得到所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径。(5)对步骤(4)得到的每个起点到每个终点之间、且处于预设的路径阈值d范围内的所有路径进行降序排序处理，以得到每个起点到所有终点中的路径数量最大值及其对应的终点，该终点即道路网选址中所要选择的最相关点。2.根据权利要求1所述的基于最短路径和路径枚举的道路网选址方法，其特征在于，步骤(1)首先是从snap数据集官网上获取真实道路网络数据集，然后，利用函数read_vertex()从该真实道路网络数据集中提取顶点文件，随后，从顶点文件中获取所有顶点的数据，每条顶点数据包括顶点编号和其对应的经纬度，然后，将每个顶点的经纬度存储在一个顶点集合中；其后，利用函数read_edge()从该真实道路网络数据集中提取边文件，随后，从边文件中获取所有边的数据，每条数据包括边起点和终点的编号，然后，将每条边起点和终点的编号存储在一个边集合中；其后，依次从边集合中取出每条边起点和终点的编号，根据起点和终点的编号从顶点集合中取出对应的经纬度，然后，根据这两个顶点的经纬度计算出边的权重；随后，将计算得到的任意两个顶点之间的权重添加到边集合中；最后，根据边集合里存储的边数据与其对应的权重建立一个无向有权图。3.根据权利要求1或2所述的基于最短路径和路径枚举的道路网选址方法，其特征在于，边的权重是根据如下算式计算得到的：其中r表示地球半径；分别表示顶点1和顶点2的纬度；λ1、λ2分别表示顶点1和顶点2的经度。4.根据权利要求1至3中任意一项所述的基于最短路径和路径枚举的道路网选址方法，其特征在于，步骤(2)包括以下子步骤：(2-1)设置计数器i＝0；(2-2)判断计数器i是否小于等于迭代总数m，如果是则进入步骤(2-3)，否则过程结束；(2-3)对无向有权图进行读取操作，以得到无向有权图的所有顶点，利用函数rand()随机生成一个起点，随后，将生成的起点插入到起点集合，该起点集合初始为空。5.根据权利要求1所述的基于最短路径和路径枚举的道路网选址方法，其特征在于，步骤(3)包括以下子步骤：(3-1)设置计数器j＝0；
(3-2)判断计数器j是否小于等于迭代总数n，如果是则进入步骤(3-3)，否则过程结束。(3-3)对无向有权图进行读取操作，以得到无向有权图的所有顶点，利用函数rand()随机生成一个终点，随后，进入步骤(3-4)；(3-4)设置计数器k＝0；(3-5)判断计数器k是否小于等于起点集合的大小m，如果是，则进入步骤(3-6)，否则设置j＝j+1，并返回步骤(3-2)；(3-6)利用dijkstra算法计算终点集合中的第j个终点到起点集合中的第k个起点的最短距离；(3-7)判断得到第j个终点到第k个起点的最短距离是否小于或等于预设的路径阈值d，如果是，则进入步骤(3-8)，否则设置k＝k+1，并返回步骤(3-5)。(3-8)将第j个终点插入到终点集合，该终点集合初始为空。6.根据权利要求1所述的基于最短路径和路径枚举的道路网选址方法，其特征在于，步骤(4)包括以下子步骤：(4-1)设置计数器a＝0；(4-2)判断计数器a是否小于等于起点集合的大小m，如果是则进入步骤(4-3)，否则过程结束；(4-3)设置计数器b＝0；(4-4)判断计数器b是否小于等于终点集合的大小n，如果是则进入步骤(4-5)，否则设置a＝a+1，并返回步骤(4-2)；(4-5)使用dijkstra算法计算无向有权图中除了第b个终点以外的每个顶点到终点b的最短距离，并将计算得到的多个最短距离存储在一个数组sd中，该数组sd初始为空；(4-6)设置计数器c＝0(其用于记录每个起点到每个终点满足预设的路径阈值d范围内的路径数量)，初始化集合visited为空(该集合用于存储已搜索过的顶点)，初始化已搜索的路径距离dis为零，并将起点集合中的第a个起点作为当前搜索顶点v；(4-7)判断当前搜索顶点v是否等于终点集合中的第b个终点，如果是，则设置c＝c+1，然后进入步骤(4-13)，否则进入步骤(4-8)；(4-8)将当前搜索顶点v插入到集合visited中，并进入步骤(4-9)；(4-9)获取当前搜索顶点v的邻居顶点w，并进入步骤(4-10)；(4-10)判断邻居顶点w是否位于集合visited中，如果是，则表示该顶点已访问过，不必重新搜索避免重复，并返回步骤(4-9)，否则进入步骤(4-11)；(4-11)判断邻居顶点w是否同时满足以下两个条件：
①
已搜索的路径距离dis(dis＝dis+邻居顶点w到当前搜索顶点v之间的距离)是否小于等于预设的路径阈值d；
②
由步骤(4-5)计算得到的顶点w到终点b的最短距离sd[w]+已搜索的路径距离dis是否小于等于预设的路径阈值d，如果是，则进入步骤(4-12)，否则对邻居顶点w进行剪枝操作，停止访问邻居顶点w的所有邻居顶点；(4-12)将第a个起点的邻居顶点w作为当前搜索顶点v，并返回步骤(4-7)；(4-13)将集合visited中的所有顶点清空，并返回起点集合中的第a个起点到终点集合中的第个终点b的路径数量c。7.一种基于最短路径和路径枚举的道路网选址系统，其特征在于，包括：
第一模块，用于读取真实道路网络数据集，提取其中的顶点和边数据，并根据提取的顶点和边数据建立无向有权图；第二模块，用于使用函数readgraph()对第一模块得到的无向有权图进行读取处理，以得到起点集合；第三模块，用于使用函数readgraph()对第一模块得到的无向有权图进行读取处理，以得到终点集合；第四模块，用于使用深度优先搜索dfs方法对第二模块得到的起点集合和第三模块得到的终点集合进行处理，以得到所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径。第五模块，用于对第四模块得到的每个起点到每个终点之间、且处于预设的路径阈值d范围内的所有路径进行降序排序处理，以得到每个起点到所有终点中的路径数量最大值及其对应的终点，该终点即道路网选址中所要选择的最相关点。

技术总结
本发明公开了一种基于最短路径和路径枚举的道路网选址方法，首先读取真实道路网络数据集，提取其中的顶点和边数据，并根据提取的顶点和边数据建立无向有权图，使用函数readGraph()对无向有权图进行读取处理，以得到起点集合，使用函数readGraph()对无向有权图进行读取处理，以得到终点集合，使用深度优先搜索DFS方法对起点集合和终点集合进行处理，以得到所有起点到所有终点之间、且处于预设的路径阈值d范围内的所有路径，对每个起点到每个终点之间、且处于预设的路径阈值d范围内的所有路径进行降序排序处理，以得到每个起点到所有终点中的路径数量最大值及其对应的终点。本发明能够解决现有基于Dijkstra算法的道路网选址方法查询效率低的技术问题。道路网选址方法查询效率低的技术问题。道路网选址方法查询效率低的技术问题。


技术研发人员：周旭 吴凯莉 余婷 张吉 杨志邦 李肯立
受保护的技术使用者：之江实验室
技术研发日：2023.04.03
技术公布日：2023/7/22