基于路径和权的最短路径搜索方法

摘要

本发明旨在提供一种基于路径和权的最短路径搜索方法，包括以下步骤：1）每段路的路径长度为真实距离除以权值；2）将待分析区域内各条道路连接；3）连接起始点和终点得到连接线，得到多个初始路径多边形；4）将多个初始路径多边形合并，得到外包多边形；5）以连接线为界，取得外包多边形的起始左路径及起始右路径；6）用较短的连线代替起始路径对应两点的连接线，依次搜索得到新左路径和新右路径；7）若新左路径和新右路径有重叠，重叠部分必为最短路径部分，若新左路径和新右路径未重叠，得到最终左路径和最终右路径；8）合并最终左路径和最终右路径内的中间多边形，得到合并多边形；9)将新左右路径公共部分与求得的结果合并，得到最终最短路径。本发明搜索效率和精度高，可在当前各大空间数据处理软件平台实现。

说明书

技术领域

本发明涉及数学与计算机图形学领域，具体涉及一种基于路径和权的最短路径搜索方法。

背景技术

最短路径搜索常见有Dijkstra算法(单源最短路径)、Floyd算法(插点法)、AStar算法(启发式最短路径算法)等，其中最著名的算法是Djikstra算法。此算法的实现基于图的邻接矩阵表示法，它不仅能够找到任意两点的最短路径，还可以找到某个指定点到其他所有顶点的最短路径。Dijkstra算法虽然简单，但需搜索范围内所有路径，如网内节点数非常大，则计算效率将急剧下降。Floyd算法的优点是提出了初始条件，避免了Dijkstra算法搜索的无目的性，搜索效率有很大提高，但是其假设的初始路径仍与整个搜索范围内节点数有关，搜索效率依然不高且最终结果不一定是最短路径。AStar算法实际是一种启发式搜索，就是利用一个估价函数评估每次搜索的路径，决定选用合适的评估函数。这样可以极大的优化普通的广度优先的路径搜索，但是搜索准确度受到估价函数的影响，其结果不一定是最短路径。

以上方法虽然可以实现最短路径搜索问题，但存在如下缺点和不足：1）搜索效率低，搜索结果与效率难以得到均衡；2）处理过程复杂，算法虽然成熟，却未能结合空间关系提升搜索效率和准确率；3）道路情况各异，当前最短路径搜索算法多考虑几何最短路径，很少能动态及时根据路况实时更新最短路径且需要重新再次搜索。

发明内容

本发明的目的在于提供一种基于路径和权的最短路径搜索方法。本发明将结合各种算法的优点，提出一种全新的最短路径搜索算法，将最短路径搜索扩展到面层，利用点线面的拓扑关系，实现不受搜索范围影响的、可根据道路情况调整权值、简单高效的最短路径搜索。

本发明的技术方案如下：本发明的基于路径和权的最短路径搜索方法，包括以下步骤：

1）首先将不同类型的道路赋予不同的权值，每段路的路径长度为真实距离除以权值；

2）再将待分析区域内各条道路连接，空间拓扑分析，将区域内的道路线构面；

3）直线连接起始点和终点得到连接线，对连接线通过地理信息系统平台的空间查询功能进行空间查询分析，得到与连接线空间相交的多个初始路径多边形；

4）将得到的多个初始路径多边形通过地理信息系统平台合并，得到外包多边形；

5）以连接线为界，方向为起始点到终点，取得外包多边形的起始左路径及起始右路径，取起始左路径和起始右路径为起始路径；

6）以该起始路径为准，从起始点开始，依次检查多个路径多边形，若起始路径中该段两端的连接线路径长度大于对应路径多边形中另一边的连线的路径长度，用较短的连线代替起始路径对应两点的连接线，依次搜索得到新左路和新右路径；

7）以新左路径和新右路径为起算，若新左路径和新右路径有重叠，新左右路径公共部分，则重叠部分必为最短路径部分，若新左路径和新右路径未重叠，以新左路径和新右路径的相交点为分割点，将相邻的新左右路径多边形中新左路径和新右路径通过的、且具有公共边的多边形合并，重复以上步骤6、7，得到最终左路径和最终右路径；

8）合并最终左路径和最终右路径内的中间多边形，得到合并多边形，求得两相邻左右路径交点间的路径，取短者为结果；

9)再次将新左右路径公共部分与求得的结果合并，得到最终最短路径。

上述步骤1)包括以下步骤：

11)首先将道路根据不同的等级，分别赋予不同的权值；

12)取得每段道路的实际长度；

13)将长度与权值相除，得到每段路的路径长度。

上述步骤2)包括以下步骤：

21)通过地理信息系统平台检查道路连接拓扑错误，确保每条道路正确的连接关系；

22)通过地理信息系统平台进行空间拓扑分析，将区域内的道路拓扑构面；

23)通过地理信息系统平台检查拓扑构面错误，如出现断头路等，不参与构面；

24)构面成功后的多边形应该依次相连，共点或共边；

25)若出现未依次相连的多边形，检查错误，若存在错误，重复步骤22)、23)、24)；

26)若不存在错误，则未连接多边形之间路径孤立边必为最短路径的一部分，记录该孤立线段。

上述步骤3)包括以下步骤：

31)连接起始点和终点，得到两点间的连接线，即为两点间的理论最短距离；

32)以连接线为准，通过地理信息系统平台空间查询与连接线有空间相交的多个初始路径多边形。

上述步骤4)包括以下步骤：

41)通过地理信息系统平台检查查询得到多个初始多边形，若依次相连，则将多边形地理信息系统平台合并，得到外包多边形，进入步骤5）；

42)若存在不相连情况，则通过地理信息系统平台将相连的部分多边形合并，转入步骤43）；

43)记录合并后的外包多边形，若存在孤立线，该连线路径必为最短路径的一部分。

上述步骤5)包括以下步骤：

51)以连接线为界，方向为终点到起始点；

52)若路径多边形不连接，以孤立线为公共部分，则左右边线与孤立线分别相连即为左边线和右边线；

53)若路径多边形连接，取得该外包多边形的起始左路径及起始右路径，作为起始路径。

上述步骤6)包括以下步骤：

61)以该起始路径为准，从起始点开始，依次检查多个初始路径多边形，若起始路径中该段两端的连接线路径长度大于路径多边形中另一边的连线的路径长度，用较短的连线代替起始路径对应两点的连接线；

62)依次搜索每一个路径多边形，得到新左路径和新右路径。

上述步骤7)包括以下步骤：

71)若新左路径和新右路径有重叠，则重叠部分必为最短路径部分；

72）若新左路径和新右路径未重叠，以新左路径和新右路径相交点为分割点，将相邻新左路径和新右路径通过的、且具有公共边的左右路径多边形合并：

73）重复以上步骤6、7，得到最终左路径和最终右路径。

上述步骤8)包括以下步骤：

81)合并最终左路径和最终右路径包含的路径中间多边形，得到合并多边形；

82）以合并多边形为准，求得两相邻分割点间的最短左路径和最短右路径，取短者为结果。

上述步骤9)包括以下步骤：

91）若不是是断头路，再次将新左右路径公共部分与求得的结果合并，得到最终最短路径19；

92）若是断头路，搜索得到的最短路径连接断头路即为最终的最短路径。

本发明的最短路径搜索方法优选用城市复杂道路情况的最短路径搜索环境。本发明通过将最短路径搜索方法的传统算法扩展到空间领域，利用空间关系及最短路径的要求，既实现了初始路径的快速化确定，搜索算法的科学化，又实现了搜索过程效率的高效化。该方法可以在各大空间数据处理平台实现，具有原理简单，易于实现，高效稳定的特点，可以大大提升搜索效率和准确度。

附图说明

图1为本发明基于路径和权的最短路径搜索方法的流程示意图；

图2至图9为本发明基于路径和权的最短路径搜索方法实施例的搜索过程示意图。。

具体实施方式

下面结合实施例详细阐述本发明。

实施例1

本实施例基于路径和权的最短路径搜索方法，包括以下步骤：

本实施例某市主城区两点间最短路径搜索，运行平台为PC上的Windows7操作系统，地理信息系统开发平台为北京超图地理信息平台软件5.3.3版本。

为了准确定义概念，确保语言表述的正确性及便于程序实现，特对以下内容进行说明及定义：

节点：道路的特征点；

度：节点连接线的条数，度为2是为普通节点，度大于2为结点；

结点：不同道路的交点；

道路：自然道路；

路径多边形：所有弧段围成的区域。

四者关系：节点为道路的特征点，两端（度大于2）时，即为结点。临近结点连线即为弧段，结点的度大于2。弧段为这些多边形的边界，每个弧段为两个相邻多边形的公共边即空间关系为相交。

具体步骤如下：

1)首先将不同类型的道路赋予不同的权值，每段路的路径长度为真实距离除以权值；

2)再将待分析区域内各条道路连接，通过北京超图地理信息平台软件的空间拓扑功能进行分析，将区域内的道路线通过北京超图地理信息平台软件的空间数据处理功能构面；

3)直线连接图2所示起始点1和终点2，对连接线3通过北京超图地理信息平台软件的空间查询功能进行空间查询分析，得到与该连接线3空间相交的多个图2所示的初始路径多边形4；

4)、通过北京超图地理信息平台软件将初始路径多边形4合并，得到该连接线的图2所示外包多边形5；

5）以图2所示连接线3为界，方向为图2终点1到图2起点2，取得图3外包多边形1的初始左路径6及初始右路径7，取图3初始左路径6和初始右路径7为起始路径；

6）以该起始路径为准，从图2起点1开始，依次检查图2多个路径多边形4，若起始路径中该段两端的连接线路径长度大于对应路径多边形中另一边的连线的路径长度，用较短的连线代替起始路径对应两点的连接线，依次搜索得到图4所示新左路径9和新右路径10；

7）以图4所示新左路径9和新右路径10起算，若新左路径9和新右路径10重叠，则重叠部分图4所示的新左右路径公共部分11必为最短路径部分，若新左路径9和新右路径100未重叠，以相邻的图5所示的左右路径交点15为分割点，通过北京超图新左路径9和新右路径10通过的、且具有公共边的左右路径多边形合并，重复以上步骤6、7，得到最终的路径13和最终右路径14；

8）合并图5所示最终左路径13和最终右路径14内的多边形，得到图6所示的合并多边形16，求得两相邻图5所示的最终左右路径交点15间左右两边的路径，取短者为结果；

9)通过北京超图地理信息平台软件的空间数据处理功能，再次将图4所示的新左右路径公共部分11与求得的结果合并，得到图8所示最终最短路径19。

步骤1包括以下步骤：

11）首先将道路根据不同的等级，分别赋予不同的权值P，如主干道权值为1，次干道为0.8，支路为0.6；

12）取得每段道路的实际长度L；

13）将长度与权值相除，得到每段路的路径长度L/P；

步骤B包括以下步骤：

21）通过北京超图地理信息平台软件检查道路连接拓扑错误，对具有拓扑错误的路径进行检查，确保每条道路正确的连接关系；

22)通过北京超图地理信息平台软件进行空间线拓扑，将区域内的道路拓扑构面；

23）再次通过北京超图地理信息平台软件检查拓扑构面错误，如出现断头路即检查完毕后依然存在拓扑错误的道路，不参与构面；

24）通过北京超图地理信息平台软件构面成功后的多边形应该依次相连，共点或共边，空间关系为面面之间相切；

25）若出现未依次相连的多边形，检查错误，若存在错误，重复22）、23）、24）；

26）若不存在错误，则未连接多边形之间路径图9所示孤立路径1必为最短路径的一部分，记录该孤立线段；

步骤3）包括以下步骤：

31）若图2所示起始点1或图2所示终点2在断头路上，则将起始点1或终点2沿断头路搜寻到对应的路径多边形，以断头路与路径多边形的交点作为起始点1或终点2；

32）连接图2所示起始点1和图2所示终点1，得到两点间的图2所示连接线段3，即为两点间的理论最短距离；

33）以连接线段为准，通过北京超图地理信息平台软件空间查询与连接线有空间相交的图2所示的多个路径多边形4；

步骤4包括以下步骤：

41）通过北京超图地理信息平台软件空间查询得到的多个路径多边形4，若依次相连，则通过北京超图地理信息平台软件的空间数据处理功能将多边形合并得到图3所示的外包多边形5，进入步骤5）；

42)若存在不相连情况，则通过北京超图地理信息平台软件将相连的部分多边形合并得到图3所示的外包多边形5，转入43）；

43)记录合并后的外包多边形之间连线图9所示孤立线20，该连线路径必为最短路径的一部分；

步骤5包括以下步骤：

51)以图2所示连接线3为界，方向为图2所示终点2到图2所示起始点1，取得图3所示外包多边形5的初始左边线6和初始右边线7；

52）若路径多边形不连接，则图9所示左边线21和右边线22与孤立线20分别相连即为初始左边线6和初始右边线7；

53）以初始左边线6和初始右边线7为起始路径，进入步骤6；

步骤6）包括以下步骤：

61）以该起始路径为准，从起点开始，依次检查图2所示的多个初始路径多边形4，若起始路径中该段两端的连接线路径长度大于路径多边形中另一边的连线的路径长度，用较短的连线代替起始路径对应两点的连接线；

62）依次搜索每一个路径多边形，得到新的图4所示新左路径9和新右路径10；

步骤7）包括以下步骤：

71）以图4所示新左路径9和新右路径10为起算，若新左路径9和新右路径10有重叠图4所示的新左右路径公共部分11，则重叠部分必为最短路径部分；

72）若新左路径9和新右路径10未重叠，以图5所示的临近左右路径交点15为起始点，通过北京超图地理信息平台软件的空间数据处理功能将相邻、新左路径9和新右路径10通过的且具有公共边的多边形合并；

73）重复以上步骤6、7，最终得到图5所示的最终左路径13和最终右路径14，最终左路径13和最终右路径14的交点是最终左右路径交点15；

步骤8）包括以下步骤：

81）通过北京超图地理信息平台软件的空间数据处理能力合并图5所示最终左路径13和最终右路径14内的多边形，得到图6所示的多个合并多边形16；

82）求得两相邻分割点间左右两边的最短左路径17和最短右路径18，图7所示，取短者为结果；

步骤9包括以下步骤：

91）若不是是断头路，再次将图4所示的新左右路径公共部分11与求得的结果合并，得到图8所示最终最短路径19；

92）若是断头路，搜索得到的最短路径连接断头路即为最终的最短路径。