图论最短路径问题 在消防选址中的应用
【摘 要】 最短路径问题是图论解决的典型实际问题之一,可用来解决管路铺设、线路
安装、厂区布局和设备更新等实际问题。
介绍了图论最短路径问题及其算法,并应用图论最短路径问题的分析方法,解决城市消防站的选址问题。
【关键词】 最短路径;Floyd 算法;消防
1 引言
图论是运筹学的一个重要分支,旨在解决离散型的优化问题,近年来发展十分迅速。
在人们的社会实践中,图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。
图论中的“图”,并不是通常意义下的几何图形或物体的形状图,也不是工程设计图中的“图”,而是以一种抽象的形式来表达一些确定的对象,以及这些对象之间具有或不具有某种特定关系的一个数学系统。
也就是说,几何图形是表述 物体的形状和结构,图论中的“图”则描述一些特定的事物和这些事物之间的联系。
它是数学中经常采用的抽象直观思维方法的典型代表。
2 图论基本概念
2.1 图的定义
有序三元组),,(ϕE V G =称为一个图,其中:
(1)),,,(21n V V V V =是有穷非空集,称为顶点集,其元素叫做图的顶点; (2)E 称为边集,其元素叫做图的边;
(3)ϕ是从边集E 到顶点集V 的有序或者无序对集合的影射,称为关联函数。
2.2 图的分类
在图G 中,与V 中的有序偶),(j i V V 对应的边e 称为图的有向边(或弧),而与V 中顶点的无序偶对应的边e 称为图形的无向边,每一条边都是无向边的图,叫做无向图,记为
),(E V G =;每一条边都是有向边的图叫做有向图,记为),(E V D =;既有无向边又有有
向边的图叫做混合图。
2.3 权
如果图G 中任意一条边),(j i V V 上都附有一个数ij W ,则称这样的图G 为赋权图,
ij W 称为边),(j i V V 上的权。
3 最短路径问题
最短路径问题是图论中的一个基本问题。
在赋权图中,每条边都有一个数值(长度、成本、时间等),找出两节点之间总权和最小的路径就是最短路径问题。
最短路径问题,通常归属为三类:
(1)单源最短路径问题:包括确定起点的最短路径问题和确定终点的最短路径问题。
确定终点与确定起点的最短路径问题相反,该问题是已知终点,求最短路径问题。
在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
(2)确定起点终点的最短路径问题:即已知起点和终点,求两结点之间的最短路径。
(3)全局最短路径问题:求图中所有的最短路径。
4 最短路径算法
在赋权图中寻求最短路的算法通常有两种:Dijkstra 算法和Floyd 算法。
4.1 Dijkstra 算法
当所有的权数0≥ij W 时,Dijkstra 算法是目前公认的最好的算法。
其基本思想是从起点0v 出发,逐步向外发展。
探索过程中,每到一个点,都记录下路径与路程,称为这个点的标号。
故Dijkstra 算法也称为标号法。
具体标号由两部分构成,第一部分是一个字母,表示前面的一个点的符号,说明从哪里来;第二部分是一个数字,表示从起点到目前位置的距离,说明有多远。
标号被分成临时标号和永久标号两种。
前者是可以修改的,后者是不变的。
开始的时候,所有的标号都是临时标号,每一次算法循环,将其中的某一个临时标号改变为永久标号。
因此,最多经过1-n 次,可以求出从起点到终点的最短路径和路程。
Dijkstra 的算法步骤为:设起点为0v ,终点为n v 。
(1)起点标号(一,0),邻点标号)),(,(00v v L v ,其他标号),(0∝+v 。
令0v V V -=。
(2)如果φ=V ,终止算法。
(3)选择V v k ∈,具有最小标号{})(min )(i V
v k v L v L i ∈=。
如果n k v v =,
终止算法;否则,将k v 的标号改成永久标号,令k v V V -=。
(4)检查k v 的邻点,如果
)()()(i k k i v v L v L v L ++>,则给i v 标号))()()(,(i k k i k v v L v L v L v ++>并返回步骤(2)。
4.2 Floyd 算法
在某些问题中,需要确定图中任意两点之间的最短路径与路程。
如采用Dijkstra 算法求解,则须依次变换起点,重复执行算法n 次才能得到所需结果,这显然过于繁琐。
Floyd 算法可以借助于权矩阵直接求出任意两点之间的最短路径。
首先定义赋权图的权矩阵:n n ij d D ⨯=][这里
⎩⎨
⎧∝∈=否则
当,),(,E
v v d j i ij ij ω 式中,ij w 表示),(j i v v 的权数。
Floyd 的算法步骤:(1)令0=k ,输人权矩阵D D =)0(。
(2)令1+=k k ,计算
n k d D n n k ij k ,,2,1,)()1()( ==⨯- ,式中],,min[)
1()1()1()(---=k kj k ik k ij k ij d d d d 。
(3)如果n k =,
终止算法;否则,返回步骤(2)。
上述算法的最终结果n n n ij n d D ⨯=)()()(中元素)
(n ij
d 就是从顶点i v 到j v 的最短路程。
如果希望计算结果不仅给出任意两点间的最短路程,而且给出具体的最短路径,则在运算过程中要保留下标的信息,即ikj kj ik d d d =+。
5 最短路径问题在消防站选址中的应用
某城市的开发区中要建一个消防站,该开发区的示意图如图1所示,其中10
21,,,v v v 表示开发区中10个消防重点单位,考虑到交通路况,部分单位之间往返的距离不完全相同,分析消防站选址问题。
消防站选址应该遵循到达各个点的距离尽可能短的原则为最好,这样才能做到在火灾发生时尽快赶到火灾现场而不延误灭火时机。
在图1中任取一点V v i ∈,考虑i v 与V 中其他顶点间的距离),(),,(),,(21n i i i v v d v v d v v d ,把这n 个距离中最大数称为顶点i v 的最大服务距离,记做)(i v e 。
要使消防车到达各个点的距离尽可能的短,应选取最大服务距离最小的点,即)](,),(),(m in[)(1021v e v e v e v e i =。
图l 的权矩阵为:
10
9
87
65
43
2
1
0535062603143210652097468029508172802340939
0v v v v v v v v v v D ⎥⎥
⎥⎥⎥
⎥⎥⎥⎥⎥⎥
⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢
⎢⎢⎢⎢⎢⎢⎣⎡∝∝∝∝∝∝
∝
∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝=
109
8
7
6
5
4
3
2
1
v v v v v v v v v v
用Floyd 算法进行计算,得到各个节点之间的最短距离如表l ,其中任意两顶点的最短
路线如表2。
由表1可知:
14)(1=v e , 12)(2=v e , 11)(3=v e , 8)(4=v e , 9)(5=v e , 10)(6=v e , 10)(7=v e , 9)(8=v e , 12)(9=v e , 13)(10=v e
其中4v 点具有最小的最大服务距离,所以把消防队建在4v 最合理。
6 结束语
在实际工作中,我们可以应用图论中最短路径问题的分析方法,科学合理的解决城市中消防站的选址问题。
【参考文献】
[1]李荣钧,邝英强.运筹学[M].广州:华南理工大学出版社,2002. [2]任善强,雷鸣.数学模型[M].重庆:重庆大学出版社,2006.
[3]郭耀煌.运筹学原理与方法[M].成都:西南交通大学出版社,1994.。