图论中最短路径问题

《图论中最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论最短路径问题在消防选址中的应用【摘要】最短路径问题是图论解决的典型实际问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。介绍了图论最短路径问题及其算法，并应用图论最短路径问题的分析方法，解决城市消防站的选址问题。【关键词】最短路径；Floyd算法；消防1引言图论是运筹学的一个重要分支，旨在解决离散型的优化问题，近年来发展十分迅速。在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。图论中的“图”，并不是通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一

2、些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统。也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系。它是数学中经常采用的抽象直观思维方法的典型代表。2图论基本概念2.1图的定义有序三元组称为一个图，其中：(1)是有穷非空集，称为顶点集，其元素叫做图的顶点；(2)称为边集，其元素叫做图的边；(3)是从边集到顶点集的有序或者无序对集合的影射，称为关联函数。2.2图的分类在图中，与中的有序偶对应的边称为图的有向边(或弧)，而与中顶点的无序偶对应的边称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为；每一条边都是有

3、向边的图叫做有向图，记为；既有无向边又有有向边的图叫做混合图。2.3权如果图中任意一条边上都附有一个数，则称这样的图为赋权图，称为边上的权。43最短路径问题最短路径问题是图论中的一个基本问题。在赋权图中，每条边都有一个数值(长度、成本、时间等)，找出两节点之间总权和最小的路径就是最短路径问题。最短路径问题，通常归属为三类：(1)单源最短路径问题：包括确定起点的最短路径问题和确定终点的最短路径问题。确定终点与确定起点的最短路径问题相反，该问题是已知终点，求最短路径问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。(2)确定起点终

4、点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。(3)全局最短路径问题：求图中所有的最短路径。4最短路径算法在赋权图中寻求最短路的算法通常有两种：Dijkstra算法和Floyd算法。4.1Dijkstra算法当所有的权数时，Dijkstra算法是目前公认的最好的算法。其基本思想是从起点出发，逐步向外发展。探索过程中，每到一个点，都记录下路径与路程，称为这个点的标号。故Dijkstra算法也称为标号法。具体标号由两部分构成，第一部分是一个字母，表示前面的一个点的符号，说明从哪里来；第二部分是一个数字，表示从起点到目前位置的距离，说明有多远。标号被分成临时标号和永久标号两

5、种。前者是可以修改的，后者是不变的。开始的时候，所有的标号都是临时标号，每一次算法循环，将其中的某一个临时标号改变为永久标号。因此，最多经过次，可以求出从起点到终点的最短路径和路程。Dijkstra的算法步骤为：设起点为，终点为。(1)起点标号(一，0)，邻点标号，其他标号。令。(2)如果，终止算法。(3)选择，具有最小标号。如果，终止算法；否则，将的标号改成永久标号，令。(4)检查的邻点，如果，则给标号并返回步骤(2)。4.2Floyd算法在某些问题中，需要确定图中任意两点之间的最短路径与路程。如采用Dijkstra算法求解，则须依次变换起点，重复执行算法次才能得到所需结果，这显

6、然过于繁琐。Floyd算法可以借助于权矩阵直接求出任意两点之间的最短路径。首先定义赋权图的权矩阵：这里4式中，表示的权数。Floyd的算法步骤：(1)令，输人权矩阵。(2)令，计算，式中。(3)如果，终止算法；否则，返回步骤(2)。上述算法的最终结果中元素就是从顶点到的最短路程。如果希望计算结果不仅给出任意两点间的最短路程，而且给出具体的最短路径，则在运算过程中要保留下标的信息，即。5最短路径问题在消防站选址中的应用某城市的开发区中要建一个消防站，该开发区的示意图如图1所示，其中表示开发区中10个消防重点单位，考虑到交通路况，部分单位之间往返的距离不完全相同，分析消防站选址问题。消

7、防站选址应该遵循到达各个点的距离尽可能短的原则为最好，这样才能做到在火灾发生时尽快赶到火灾现场而不延误灭火时机。在图1中任取一点，考虑与中其他顶点间的距离，把这个距离中最大数称为顶点的最大服务距离，记做。要使消防车到达各个点的距离尽可能的短，应选取最大服务距离最小的点，即。图l的权矩阵为：4用Floyd算法进行计算，得到各个节点之间的最短距离如表l，其中任意两顶点的最短路线如表2。表1：各节点之间的最短距离1234567891010539510119131425024