最短路问题的应用

豆俊梅 孙彩贤

【摘要】社会在进步、科技在发展，随之而来的时间的分配、路线的选择等和最短路问题息息相关的问题在现在的社会变得越来越突出.最短路问题的本质就是在一定的条件下寻找出最有效的方式来达到目的，以使得结果最佳.最短路问题在理论研究和应用上都有着重要的意义.本文首先介绍最短路的算法，而后讨论它在实际中的应用以及发展前景.

【关键词】最短路问题；Dijkstra算法

一、最短路的定义

定义1若图G=G（V，E）中每一边e都给有一个实数W（e），称为边e的权，就把这种图命名为赋权图，记为G=G（V，E，W）.

定义2若图G=G（V，E）是赋权图并且有W（e）≥0，e属于与E（G），若u到Vi到Vj的路W（u）的权，则称W（u）为u的长，长最小的Vi到Vj的路W（u）的路W（u）称为最短路.

倘若要找出从Vi到Vj的路u，使的全长是最短的，即minWu=∑ei∈uWe.

二、Dijkstra算法

在计算最短路问题时，一种方法是图论的最基本算法Dijkstra算法，它是用于在最短的计算时间内寻找所有节点最短的路径，我们通常用来解决两个点之间最短路径上的加权图的算法，是把时间节点的Dijkstra算法重复N次.

Dijkstra算法：

令s=vi，i=1，=v2，v3，…，vn，

并令Wv1=0，Tvj=∞，vj∈.

1对vj∈，求minTvj，Wvi+wij=Tvj.

2求minvj∈sTvj得Tvk，使Tvk=minvi∈sTvj，令Wvk=Tvk.

3若vk=vn则已找到v1到vn的最短路距离Wvk，否则令i=k从中删去vi转1.

这样经过有限次迭代则可以求出v1到vn的最短路线，

三、最短路问题的应用

在平时生活中火灾是发生较为频繁的一种灾害，其带来的损失也是巨大的.倘若在火灾发生后能够通过消防的一些措施有效的来控制火势，毫无疑问时间是最重要的，短暂的时间可以有效的使火灾所带来的损失大大减少，火灾所带来的经济损失常常是不可预测的，这与火灾的持续时间、燃烧面积、火灾场地等因素都有着必不可分的联系.对于我们平时生活中常发生火灾的位置和火灾所带来损失的数据统计可以知道主要与火灾的持续时间有关.这就对消防队的到达时间有着很重要的关系，只有及时到达火灾现场并作出相应的措施才能降低火灾做带来的损失.基于我国的通讯、道路和消防设备的实际情况以及对大量的火灾案例分析可以得出只有在15分钟内到达火灾现场作出灭火措施才能有效的防止火势蔓延并可以有效的扑灭火灾.但是由于在实际的消防资源调度等方面的各种不及时，常常使得消防人员不能及时到达火灾现场，以致丢失了好的救灾时机，而我们运用地理信息中的Dijkstra最短路径的算法就可以解决如何快速调动消防救援到达火灾现场的问题.

运用Dijkstra最短路径的算法中，可以通过计算路径的边权来衡量最短路径，算法参数标准建立的重要因素是确定边权以使得所设定的边权更符合系统的需要，边权值设定的好坏直接决定了算法的适用性.在现在的交通网络中路线最短不一定就是耗时最短的路径，基于此如何选择合适的权值是设计最优路线的重要前提.交通，天气，车道数，道路状况等都是影响消防车到火灾现场的重要因素.我们把最优目标设定为救援时间最短，这样我们就可以研究道路的权重.一般而言，可以采用下面的方案来确定出行时间度量的道路权重.方案：用行程时间和阻力功能和延迟模型相交的运动模式来进行计算当时时间段的路段行程时间和交叉口延误，以此来确定权重.于是我们就可以很好的把交通流考虑了进去，很好的把实时的特点表现出来，这个方案可以很好的解决实际情况并且技术上也完全没有问题，综合考虑了实用性与可行性.

因此，把路径权值的最优指标设定为所选取的时间，并用路阻函数求出道路交通网中的各路段权值，在此基础上利用Dijkstra最短路径算法实现消防力量掉级的最优化.

四、小结

最短路问题是现代运筹学的重要组成部分，也是经济学所研究的重要课题之一，最短路问题及应用的重要性越来越多的被人们所认识.随着科学技术的和生产的发展，最短路定义的内涵也在不断地丰富、外延不断延伸.最短路问题的应用在现实生活中的日益广泛，在社会生产和实践中发挥着越来越重要的作用.最短路问题的研究理论和方法的发展源于实践也服务于实践.最短路问题的要求，合理设定约束条件，通过数学上的分析运算得出各种求得最短路的方案，最后结合实际提出综合性的合理安排，达到最好的效果.最短路问题在数据结构这门课程中有涉及.在最求高效率的社会生活中最短路问题及应用也是一个较大的研究领域，一个最具潜力的领域.

所以最短路问题及它的应用的研究对于我们现在的生活有着很大的影响，在这样一个最求高效率的社会生活中，我们还要坚持不懈的进行研究，来造福全人类.

【参考文献】

[1]卜月华.图论及其应用[M].南京：东南大学出版社，2000.

[2]余为波，王涛.基于图论的舰船通道路线优化[J].2008.

[3]李玲.最短路问题在运输网络中的应用[J].2006.

[4]戴文舟.交通网络中最短路径算法的研究[D].重庆大学硕士学位论文，2004.

[5]谢灼利，等.地铁车站站台火灾中人员的安全疏散[J].中国安全科学学报，2004，14（7）：21.

[6]荣玮.基于道路网的最短路径算法的研究与实现[D].武汉理工大学硕士学位论文，2005.