图论最短路径问题

1、图论最短路径问题信息与治理科学学院信息与计算科学系课程论文课程名称：图与网络优化论文名称：图论最短路径问题在消防选址中的应用姓 名：武冬冬班 级：12 级金数二班指导教师：王亚伟学 号： 1210110057实验室：信息治理实验室日 期： 2021.06.06图论最短路径问题在消防选址中的应用1210110057 武冬冬【摘 要】 最短路问题是一类重要的优化问题, 它不仅可以直接应用于解决生 产实际中的许多问题,如管道铺设、线路安排、厂区布局、设备更新等,而且 还经常作为一个根本工具,用于解决其他优化问题.本文介绍了图论最短路径 问题及其算法,并应用图论最短路径问题的分析方法,解决城市消防站的

2、选址 问题.【关键词】 最短路径；Dijkstra 算法；消防选址1引言图论是运筹学的一个重要分支,旨在解决离散型的优化问题,近年来开展十分 迅速.在人们的社会实践中,图论已成为解决自然科学、工程技术、社会科学、 生物技术以及经济、军事等领域中许多问题的有力工具之一.图论中的“图 并不是通常意义下的几何图形或物体的形状图,也不是工程设计图中的“图 而是以一种抽象的形式来表达一些确定的对象,以及这些对象之间具有或不具 有某种特定关系的一个数学系统.也就是说,几何图形是表述物体的形状和结构,图论中的“图那么描述一些特定的事物和这些事物之间的 联系.它是数学中经常采用的抽象直观思维方法的典型代表.2

3、图论根本概念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 权如果图G中任意一条边(M,Vj)上都附有一个数

4、 Wj ,那么称这样的图G为赋权 图,Wj称为边(M,Vj)上的权.3最短路径问题最短路径问题是图论中的一个根本问题.在赋权图中,每条边都有一个数 值(长度、本钱、时间等),找出两节点之间总权和最小的路径就是最短路径问 题.最短路径问题,通常归属为三类：(1)单源最短路径问题：包括确定起点的最短路径问题和确定终点的最短路 径问题.确定终点与确定起点的最短路径问题相反,该问题是终点,求最 短路径问题.在无向图中该问题与确定起点的问题完全等同,在有向图中该问 题等同于把所有路径方向反转确实定起点的问题.(2)确定起点终点的最短路径问题：即起点和终点,求两结点之间的最 短路径.(3)全局最短路径问题

5、：求图中所有的最短路径.4最短路径算法在赋权图中寻求最短路的算法通常有两种：Dijkstra 算法和Floyd算法.4.1 Dijkstra 算法当所有的权数Wj 0时,Dijkstra 算法是目前公认的最好的算法.其根本思想是从起点叫出发,逐步向外开展.探索过程中,每到一个点,都记录下路径与路程,称为这个点的标号.故 Dijkstra 算法也称为标号法.具体标号由两局部构成,第一局部是一个字母,表示前面的一个点的符号, 说明从哪里来；第二局部是一个数字,表示从起点到目前位置的距离,说明有 多远.标号被分成临时标号和永久标号两种.前者是可以修改的,后者是不变 的.开始的时候,所有的标号都是临时

6、标号,每一次算法循环,将其中的某一 个临时标号改变为永久标号.因此,最多经过n 1次,可以求出从起点到终点的最短路径和路程.Dijkstra的算法步骤为：设起点为v0,终点为vn.1起点标号一,0,邻点标号v0, Lv0, v,其他标号v0,.令V V V0 02如果V,终止算法.（3） 选才? vk V ,具有最小标号LvJ min Lm.如果vk vn ,终止算法；vi V否那么,将vk的标号改成永久标号,令V V vk.（4） 检查vk的邻点,如果Lvi Lvk Lvk v,那么给vi标号vk,LviLvk Lvk M并返回步骤2.4.2 Floyd 算法在某些问题中,需要确定图中任意两

7、点之间的最短路径与路程.如采用 Dijkstra 算法求解,那么须依次变换起点,重复执行算法n次才能得到所需结果,这显然过于繁琐.Floyd算法可以借助于权矩阵直接求出任意两点之间的最短路径.首先定义赋权图的权矩阵：D dij n n这里ii,当vi,vi Edij式中,Wj表小vi ,vj的权数.,否那么Floyd的算法步骤：1令k 0,输人权矩阵D D.2令k k 1,Kk/Zk1 Lt d O c山-Jkmini Zk1Zk1Zk11/Q 力口 申tT舁 Ddijnn,k 1,2, ,n ?立甲 djmindjdik ,dkj J o 3如果k n,终止算法；否那么,返回步骤2.上述算法

8、的最终结果Ddi/.n中元素d就是从顶点vi到vj的最短路 程.如果希望计算结果不仅给出任意两点间的最短路程,而且给出具体的最短 路径,那么在运算过程中要保存下标的信息,即 dik dkjdikj o5最短路径问题在消防站选址中的应用某城市的开发区中要建一个消防站,该开发区的示意图如图1所示,其中V1,V2, ,Vio表示开发区中10个消防重点单位,考虑到交通路况,局部单位之间 往返的距离不完全相同,分析消防站选址问题.图1消防重点单位示意圄消防站选址应该遵循到达各个点的距离尽可能短的原那么为最好,这样才能做到在火灾发生时尽快赶到火灾现场而不延误灭火时机.在图1中任取一点Vi V ,考虑Vi与

9、V中其他顶点间的距离d(Vi, Vi),d(Vi ,V2), d(Vi,Vn),把这n个距离中最大数称为顶点Vi的最大效劳距离,记做e(Vi).要使消防车到达各个点 的距离尽可能的短,应选取最大效劳距离最小的点,即e(Vi)min e(Vi),e(V2), eg).图l的权矩阵为：093Vi904V32082 7v318 020D795 64%V2V3V459 v4864v502V60123v71306 v82 605V93 50V10V5V6V7V8V9V10用Floyd算法进行计算, 顶点的最短路线如表2.得到各个节点之间的最短距离如表l ,其中任意两表1:各节点之间的最短距离123456

10、78910105r 395101191314250244998111233206278610114 I61r 30575 167r 8554280564896 109r 71060527r 8710675520123898634130569 1128r 97742305101391088534501l 一 32l 一 3l 一 324l 35223123242 3533 l323243544 2 3一 l424 2 34 235553 l5 32535324663 l63一 26368746 8577 8 53 l7 427853747 8588 5 3一 l8 3528 5 38748599

11、 7 85 319 7429 7 85 39749 78510785 31107 107 1074 2 8 5 34107一8 5789102 3263 53864 74865 856l 一 35724一735一747l 3 l 35 1 3558 797102 3-583 584 782 4 6一93 5 7一92 4 7一 103 5 7一 10479 47105758 579 57一 10668一7686 8 7一96 8 7一 1077 8678797 10886878 7 987 1099 786979 7897 10101078 6107107一81079由表1可知：e(vi)14,e(V2)12,e.)11,e(vj8,e(vs)9,e(V6)10,e(v7)10,e(v8)9,e(Vg)12,&5.)13其中V4点具