大数据最短路径算法在预警工作中的应用研究

高峰　秦尧　刘穆　嘎玛次仁

摘  要：最短路径原本是图论中的一个经典算法文通，其目的是为了寻找图中两个定点间的最短距离。它的特点是以一个起始点为中心点向外扩展到每一个节点。随着工程学在各行业的广泛应用，最短路径的应用已经不止仅限于路程算法，它还扩展到交通工程、城市建设、计算科学等领域，该文旨在研究最短路径算法的原理和代表算法——Dijkstra（迪杰斯特拉）算法，并将这种算法应用到警务工作中，希望在未来能将最短路径算法应用到警力科学分布等工作中。

关键词：最短距离  算法  路径  应用

中图分类号：TP301    文献标识码：A 文章编号：1672-3791（2019）07（b）-0013-02

1  最短路径

线性规划问题是大数据智能算法的有监督学习范畴，即存在目标变量，需要探索特征变量和目标变量之间的关系，在目标变量的监督下学习和优化算法。最短路径算法就是一个典型的线性规划问题;令S为一个源点，T为目标点，Cij>0为路径（i，j）为链路距离。于是，需要最小的Z，使

最短路径算法开始于阻抗矩阵。阻抗矩阵中的数值表示两个节点直接连接的阻抗，表示不直接连接。而后在即将分析的Dijkstra（迪杰斯拉特）算法，就是迭代计算从中心节点到其他节点的最短距离。虽然它的计算机效率并不突出，但是它的很多扩展算法或者改进算法仍然具有很强的应用性。

2  迪杰斯特拉算法分析

Dijkstra算法（迪杰斯特拉）算法主要计算一个节点到其他节点的最短路径，算法的核心是以起点为中心向外层扩散，途径每一个点，直至扩散到终结点。虽然该算法需要遍历计算所有节点，效率略低，但是却能给出多种相似的解决方案，同时可以辅助其他算法，增加迪杰斯特拉算法效率。迪杰斯特拉算法作为最短经典的经典算法，应用范围十分广泛，如图论、运筹学、数据结构等。

该算法的思想是，设有一个带权的向图，将图中的顶点集合分为两组，第一组为已求出最短路径的顶点集合，第二组为其他未确定最短路径的顶点集合，按最短路径长度的递增次序依次把第二组的顶点加入到第一组顶点中。利用递归算法一次将所有最短距离的点加入第一组集合，从而求出第一组顶点到第二组顶点的最短路径顶点之和。如举例说明，图1是一个顶点集合图。

根据上面算面解释，设置两个顶点集合，分别为S集合和U集合（见表1），根据迪杰斯特拉算法，我们可以使用数据结构节点算法，将一个顶点到其他顶点的所有路径计算出来，最后比较权的大小，最终取权值最小的为最短路径，如A到C点，有以下路径：

A->B->C=7;A->B->D->C=8;A->E->B->C=10;A->E->D->C=13

根据上面的结果，我们发现A->E是最长路径的两种，迪杰斯特拉算法可以首先放弃经过E点的可能性。

3  最短路径算法应用及开发技术

预案处置是一种警务力量安排的方法，依据多年警务事件实践的经验和相关法律法规制度的规定，总结出针对各种类型案件的行之有效的工作方法和制定的处理案件流程，使得干警在各类不同案件的处理流程具有更强的程序化和规范化，节约警力资源，实现指导员、处警员、各警种的协调配置，最大限度发挥处置效果[2]。

预警模块是根据公安机关长期经验总结出的各类案件、事件的处理方法，并将这些方法设置成未来处理相关案件的制度流程，并最终形成预案制度。预案可以分为：群体性事件处理预案、火灾爆炸处理预案、自然灾害处理预案、化学危险品处置预案等。

首先，当接警中心接到报案后，会根据案件的发生地点甚至是地理坐标位置作为查询条件，然后根据事件的具体情况选择输入一个拦截半径，以攔截半径为圆面查询该范围内的警力装备情况和相关属性信息。

其次，输入预案信息，调出方案，根据情况对比进行调整。然后，生成最短路径线路，根据第一步的拦截半径圆面合理通知警力和使用装备，最终形成理想的路径合理安排调度。为了确保事件现场的快速处置，还可以根据线路的长短安排巡警控制交通，甚至是几条线路的交通;出警的原则是“路线固定、尽量集中”。

根据以上的步骤，我们可以选用ArcGIS Engine作为最短路径的地理信息系统的开发引擎，ArcGIS Engined的功能十分强大，它既支持简单的地图应用，同时又满足对地理信息系统较高要求的分析应用。为了能够展现大数据分析中随需而变的理念，ArcGIS Engine针对程序员开发的需求增加了开发包软件，能在开发中很容易地实现动态制图和随需要变化的GIS功能，ArcGIS Engine还增加了构建定制地图的个性需求，从而为地理信息系统做出了非常好的解决方案[3]。ArcGIS Engine为了更好地灵活支持工业标准的编程环境，开发出更加睿智的地图界面，ArcGIS Engine在组件中增加协同关系组件，使地理信息系统数据和其他信息无缝对接。丰富的API接口帮助文档和示例代码使开发者不必担心开发语言不同会是开发的障碍;但是ArcGIS Engine开发包绝不是给普通用户使用，它更多是为了供开发编程人员使用，具有很强的专业性。程序员使用ArcGIS Engine开发出的应用软件，可以跨平台使用，既可以构建在基于Intel架构的微软视窗系统，也可以轻松部署在大型服务器系统，如UNIX和Linux上，程序员不必将过多的精力放在担心不同系平台的应用效果上，而是更好地将更多的聪明才智集中在软件的应用开发上。

4  结语

最短路径的应用领域广泛，既可以使用在警务的人员调配、车辆调度等领域，还可以使用在上下班高峰期的车辆红灯调低的交通疏导上，同时还可以辅助其他算法，如克里金插值算法，不仅得到点、线图形，还能根据需要设置一个面里的相关值应用，因此最短路径算法在预警应用领域非常广泛。

参考文献

[1] 李崇贵，陈峥，丰德恩，等.ArcGIS Engine组件式开发及利用[M].北京：科学出版社，2012.

[2] 姚远.公安警务调度系统的研究与实现[D].上海交通大学，2008.

[3] 许军.地理信息系统的应用[D].北京邮电大学，2009.