【《最短路径算法验证与应用案例探析》1500字】

最短路径算法验证与应用案例分析下文将以深圳市区和上海市区的道路交通网的数据为例，对基于pgRouting的最短路径算法实现的具体过程进行描述。然后，对改进后的算法与几种经典算法的最短路径算法进行对比，包括路径质量和计算时间；同时，实现几种算法结果的可视化。1.1开源Postgresql和pgRouting配置目前谷歌地图、百度地图等都提供路径分析功能服务的接口，支持系统和用户两种分析模式，以及普通公路优先、最少花费、最短路径、最短时间等多种分析类型。基于网络类数据设置兴趣点的起始点、终止点以及途径点和故障点等信息，调用路径分析功能服务接口，可将获取到的最佳路径信息绘制到客户端。1.安装pgRouting（1）在window10系统下，安装PostgreSQL、pgAdmin、pgRouting图3：PostgreSQL下载页面图4：pgAdmin下载页面（2）使用pgAdmin4连接PostgreSQL，并建立数据库localhost:图5：新建数据库（3）创建PostGIS、pgRoutingcreateextensionpostgis;createextensionpgrouting;图6：创建postGIS、pgrouting2.准备数据（1）下载深圳市的城市交通路网的实际数据，下载为shapefile格式的数据，下载地址：GeofabrikDownloadServer图7：准备数据图8：数据展示3.将数据导入数据库（1）使用QGIS将数据导入新建的localhost数据库。注意要将注意要将multilinestring转换为linestring。图9：QGIS图10：添加shenzhen_roads.shp文件建立道路拓扑网络向shenzhen_raods中添加必要字段ALTERTABLEshenzhen_roadsADDCOLUMNsourceinteger;ALTERTABLEshenzhen_roadsADDCOLUMNtargetinteger;CREATEINDEXshenzhen_roads_source_idxONshroads(source);CREATEINDEXshenzhen_roads_target_idxONshroads(target);修改geometry字段名称ALTERTABLEshenzhen_roadsRENAMECOLUMNgeomTOthe_geom;切分道路网，生成shenzhen_roads_nodedSELECTpgr_nodeNetwork('shroads',0.00001);（a）（b）图11：（a）切分道路网时生成的表（b）表数据预览构建道路网络shenzhen_roadsnodedvertices_pgrSELECTpgr_createTopology('shroads_noded',0.00001);图12：生成表结点预览删除无效数据deletefromshenzhen_roads_nodedwheresourceisNULLandtargetisNULL;向shenzhen_roads_noded添加字段并更新数据ALTERTABLEshenzhen_roads_nodedADDCOLUMNnameVARCHAR,ADDCOLUMNtypeVARCHAR;UPDATEshenzhen_roads_nodedASnewSETname=FROMshroadsasoldWHEREnew.old_id=old.id;计算道路网距离（权重）ALTERTABLEshenzhen_roads_nodedADDdistanceFLOAT8;UPDATEshenzhen_roads_nodedSETdistance=ST_Length(ST_Transform(the_geom,4326)::geography)/1000;图13：shenzhen_roads_noded表内容预览完成数据的导入，以及初步的数据处理。1.3最短路径规划算法的实现在相同的起始结点和终点的下，运行Dijkstra算法、A*算法和改进后的双向A*算法。Dijkstra算法作为算法函数存在于PostGIS数据库中，通过pgRouting调用转换搜索实现最短路径，先决条件是必须具备每条线路的id，class(类型)，distance(长度)，name(名称)，geometry(几何结构)，source(源点)，target(终点)和Topology(拓扑图)，其中最重要的是在导入PostgreSQL数据库时要确保数据提供了一个正确的网络拓扑，包括源和各路段的目地ID信息。图14：Dijkstra算法运行结果A*算法同样存在于PostGIS数据库中，可以通过pgRouting调用转换搜索实现最短路径，先决条件是必须具备每条线路的id，class(类型)，distance(长度)，name(名称)，geometry(几何结构)，source(源点)，target(终点)和Topology(拓扑图)，x1、x2、y1、y2。图14：A*算法运行结果双向A*算法函数创建：图15：创建改进算法算法运行：图16：双向A*运行结果1.4算法对比分析在相同的起始结点和终点状态下，对比分析三种算法的数据进行对比：序号起点终点搜索时间/ms影响行数距离/km135511052.02210721.7729666061.09924731.73338705621.53851656.83420164980.7916710.53569358002.1679911.2462193150.683739.09784164640.684849.34871289491.02511713.96981106130.64518817.92103281320.55714611.01表2：Dijkstar算法运行序号起点终点搜索时间/ms影响行数距离/km135511051.10726833.0229666060.83727048.52338705621.04847468.27420164980.7228212.41569358000.85115116.4262193150.5537311.64784164640.5238611.65871289490.72211715.44981106130.54217922.71103281320.54610713.69表3：A*算法运行序号起点终点搜索时间/ms影响行数距离/km135511050.80126129.4729666060.67826045.73338705620.79446361.98420164980.5988011.23569358000.60114315.8962193150.453729.64784164640.4138410.35871289490.58710911.31981106130.43916820.01103281320.43511212.03表4：双向A*算法上述三个表中，对比分析可以发现：在随机生成的十组不同的起始点和结点的最短路径对比中，Dijkstra算法寻找到的路径质量最高，但搜索