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