图论最短路径问题

信息与管理科学学院信息与计算科学系

课程论文

课程名称：图与网络优化

论文名称：图论最短路径问题在消防选址中的应用

姓名：武冬冬

班级： 12级金数二班

指导教师：王亚伟

学号： 1210110057

实验室：信息管理实验室

日期： 2015.06.06

图论最短路径问题在消防选址中的应用

1210110057 武冬冬

【摘 要】 最短路问题是一类重要的优化问题，它不仅可以直接应用于解决生产实际中的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且还经常作为一个基本工具，用于解决其他优化问题。本文介绍了图论最短路径问题及其算法，并应用图论最短路径问题的分析方法，解决城市消防站的选址问题。 【关键词】 最短路径；Dijkstra 算法；消防选址

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所示，其中

1021,,,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 。要使消防车到达各个点的距离尽可能的短，应选取最大服务距离最小的点，即)](,),(),(min[)(1021v e v e v e v e i =。

图l 的权矩阵为：

109

87

65

43

2

1

05350626031432106520974680295081728023409390v v v v v v v v v v D ??

???

??????

??????????

???

???

??

???∝∝∝∝

∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝∝=

1098

7

6

5

4

321

v v v v v v v v v v

用Floyd算法进行计算，得到各个节点之间的最短距离如表l，其中任意两顶点的最短路线如表2。

表1：各节点之间的最短距离

1 2 3 4 5 6 7 8 9 10

1 0 5 3 9 5 10 11 9 13 14

2 5 0 2 4 4 9 9 8 11 12

3 3 2 0 6 2 7 8 6 10 11

4 6 1 3 0

5 7 5

6

7 8

5 5 4 2 8 0 5

6 4 8 9

6 10 9

7 10 6 0 5 2 7 8

7 10 6 7 5 5 2 0 1 2 3

8 9 8 6 3 4 1 3 0 5 6

9 12 8 9 7 7 4 2 3 0 5

10 13 9 10 8 8 5 3 4 5 0

表2：任意两个顶点的最短路线

i j 1 2 3 4 5

1 —l一3—

2 l一

3 l一3—2—

4 l一3—5

2 2—3—1 —2—

3 2—

4 2—3—5

3 3一l 3—2 —3—2—

4 3—5

4 4—2—3一l 4—2 4—2—3 —4—2—3—5

5 5—3一l 5—3—2 5—3 5—3—2—4 —

6 6—3一l 6—3一2 6—3 6—8—7—4 6—8—5

7 7—8—5—3一l 7—4—2 7—8—5—3 7—4 7—8—5

8 8—5—3一l 8—3—5—2 8—5—3 8—7—4 8—5

9 9—7—8—5—3—1 9—7—4—2 9—7—8—5—3 9—7—4 9—7—8—5

10 10—7—8—5—3—1 10—7—4—2 10—7—8—5—3 10—7—4 10—7—8—5

i j 6 7

8

9

10

1 l 一3—6 l 一3—5—7 l 一3—5—8 l 一3—5—7—9 1一3—5—7—10

2 2—3—6 2—4—7 2—3—5—8 2—4—6—9 2—4—7一lO

3 3—5—8—6 3—5—7 3—5—8 3—5—7—9 3—5—7一10

4 4—7—8—6 4—7 4—7—8 4—7—9 4—7—10

5 5—8—

6 5—

7 5—

8 5—7—

9 5—7一10 6 — 6—8—7 6—8 6—8—7—9 6—8—7一10 7 7—8—6 — 7—8 7—9 7一10 8 8—6 8—7 — 8—7—9 8—7一lO 9 9—7—8—6 9—7 9—7—8 — 9—7一lO

10 10—7—8—6

10—7

10—7—8

10—7—9

—

由表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]．北京：清华大学出版社，1997． [2]任善强，雷鸣．数学模型[M]．重庆：重庆大学出版社，2006．

[3]郭耀煌．运筹学原理与方法[M]．成都：西南交通大学出版社，1994．

初中数学［最短路径问题］典型题型及解题技巧 最短路径问题中, 关键在于，我们善于作定点关于动点所在直线的对称点，或利用平移和展开图来处理。这对于我们解决此类问题有事半功倍的作用。理论依据：“两点之间线段最短” ，“垂线段最短”，“点关于线对称”，“线段的平移”“立体图形展开图”。教材中的例题“饮马问题”，“造桥选址问题”“立体展开图”。考的较多的还是“饮马问题” 。 知识点：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”。“饮马问题”，“造桥选址问题”。考的较多的还是“饮马问题” ，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。解题总思路：找点关于线的对称点实现“折”转“直” ，近两年出现“三折线”转“直”等变式问题考查。 一、两点在一条直线异侧例：已知：如图，A，B在直线L的两侧，在L上求一点P，使得PA+PB 最小。 解：连接AB,线段AB 与直线L 的交点P ，就是所求。（根据：两点之间线段最短.） 二、两点在一条直线同侧 例：图所示，要在街道旁修建一个奶站，向居民区A 、B 提供牛奶，奶站应建在什么地方，才能使从A、B 到它的距离之和最短． 解：只有A、C 、B在一直线上时，才能使AC +BC最小．作点A 关于 直线“街道”的对称点A′，然后连接A ′B，交“街道”于点C，则 点C 就是所求的点． 、一点在两相交直线内部 例：已知：如图A 是锐角∠ MON 内部任意一点，在∠ MON 的两边 OM ，ON 上各取一点B，C ，组成三角形，使三角形周长最小.

解：分别作点A 关于OM ，ON 的对称点A ′，A OM ，ON 于点B、点C ，则点B、点C 即为所求分析：当AB 、BC 和AC 三条边的长度恰好能够体现在一条直线上时，三角形的周长 最小 例：如图，A.B 两地在一条河的两岸，现要在河 上建一座桥MN ，桥造在何处才能使从A 到B 的路径AMNB 最短？（假设河的两岸是平行的直线，桥要与河垂直） 解：1.将点B 沿垂直与河岸的方向平移一个河宽到E， 2.连接AE 交河对岸与点M, 则点M 为建桥的位置，MN 为所建的桥证明：由平移的性质，得 BN∥EM 且BN=EM, MN=CD, BD ∥CE, BD=CE, 所以A.B 两地的距:AM+MN+BN=AM+MN+EM=AE+MN, 若桥的位置建在CD 处，连接AC.CD.DB.CE, 则AB 两地的距离为： AC+CD+DB=AC+CD+CE=AC+CE+MN, 在△ACE 中，∵ AC+CE >AE, ∴AC+CE+MN >AE+MN, 即AC+CD+DB >AM+MN+BN 所以桥的位置建在CD 处，AB 两地的路程最短。 例：如图，A、B 是两个蓄水池，都在河流a 的同侧，为了方便灌溉作物，?要在河边建一个抽水站，将河水送到A、B 两地，问该站建在 连接A ′，A ″，分 别交 B

八年级数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．

在直线l 上求一点P ，使PB PA -的值最大． 作直线AB ，与直线l 的交 点即为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ． PB PA -的最大值＝AB ． 【问题11】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即 为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ＇． PB PA -最大值＝AB ＇． 【问题12】“费马点” 作法 图形 原理 △ABC 中每一内角都小于120°，在△ABC 内求一点P ，使P A +PB +PC 值最小． 所求点为“费马点”，即满足∠APB ＝∠BPC ＝∠ APC ＝120°．以AB 、AC 为边向外作等边△ABD 、△ACE ，连CD 、BE 相交于P ，点P 即为所求． 两点之间线段最短． P A +PB +PC 最小值＝CD ． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有 一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．3 B ．26 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 l B A l P A B l A B l B P A B' A B C P E D C B A A D E P B C

13.4课题学习最短路径问题 六街中学：罗云膑1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A，B分别是直线l异侧的两个点，在l上找一个点C，使CA＋CB最短，这时点C是直线l与AB的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求．如图所示，点A，B分别是直线l同侧的两个点，在l上找一个点C，使CA＋CB最短，这时先作点B关于直线l的对称点B′，则点C是直线l与AB′的交点． 为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C′，连接AC′，BC′，B′C′，证明AC＋CB＜AC′＋C′B.如下： 证明：由作图可知，点B和B′关于直线l对称， 所以直线l是线段BB′的垂直平分线． 因为点C与C′在直线l上， 所以BC＝B′C，BC′＝B′C′. 在△AB′C′中，AB′＜AC′＋B′C′， 所以AC＋B′C＜AC′＋B′C′， 所以AC＋BC＜AC′＋C′B. 【例1】在图中直线l上找到一点M，使它到A，B两点的距离和最小．

分析：先确定其中一个点关于直线l的对称点，然后连接对称点和另一个点，与直线l 的交点M即为所求的点． 解：如图所示：(1)作点B关于直线l的对称点B′； (2)连接AB′交直线l于点M. (3)则点M即为所求的点． 点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题. 2.运用轴对称解决距离最短问题 运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同． 警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法．解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问． 3．利用平移确定最短路径选址 选址问题的关键是把各条线段转化到一条线段上．如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决． 解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸的方法使河的宽度变为零，转化为求直线异侧的两点到直线上一点所连线段的和最小的问题． 在解决最短路径问题时，我们通常利用轴对称、平移等变换把不在一条直线上的两条线段转化到一条直线上，从而作出最短路径的方法来解决问题． 【例2】如图，小河边有两个村庄A，B，要在河边建一自来水厂向A村与B村供水． (1)若要使厂部到A，B村的距离相等，则应选择在哪建厂？ (2)若要使厂部到A，B两村的水管最短，应建在什么地方？ 分析：(1)到A，B两点距离相等，可联想到“线段垂直平分线上的点到线段两端点的距离相等”，又要在河边，所以作AB的垂直平分线，与EF的交点即为符合条件的点． (2)要使厂部到A村、B村的距离之和最短，可联想到“两点之间线段最短”，作A(或 B)点关于EF的对称点，连接对称点与B点，与EF的交点即为所求． 解：(1)如图1，取线段AB的中点G，过中点G画AB的垂线，交EF于P，则P到A，

最短路径之Dijkstra算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B 地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法

有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 （1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 2.4 Dijkstra算法举例说明 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）

最短路径问题 摘要 在图论当中，任意两点间的最短路径问题，运用Dijkstra 算法，Flord 算法，匈牙利算法等都可以就解决这类相关问题,本文主要就是运用图论相关知识，来分析问题的。 在问题一中，需要为货车司机选择一条从地点1到地点11的最短时间问题，其实际归结为求一个两点间最短路径问题，运用运筹学中的网络模型相关知识，建立了一个一个0-1线性模型，并最终求的其结果，最短时间为21，货车司机的运输路线为1891011v v v v v →→→→。 运用Floyd 算法解决问题二，并且运用Matlab 软件编程，Floyd 算法与Matlab 软件编程所得出的结果一致，最后得出了一个最短航程表，及任意两点间的最短航程图。 本文的最大亮点在于将问题二进行更深一步的拓展，从问题实际出发，从公司的差旅费用最小出发，利用Mtlab 软件编程的出了公司到个城市间差旅费用最小图，从而更能为公司节省成本。 任意城市间差旅费用最小 其次是本文结果的准确性，问题一运用Lingo 软件编程，和WinQSB 软件，所得出结果都是一致的，问题二更是运用Floyd 算法，Matlab 软件编程，WinQSB 软件，大大地保证了结果的准确性，并且十分恰当地运用WinQSB 软件将作图功能，把每一提的最短路径都清晰的描绘出来，更加直观地将结果展现出来。 关键字：Matlab Lingo WinQSB Floyd 算法 0-1规划

一、 问题重述 问题一需要解决的问题是在一个城市交通网络中（图一），如何从地点1找到一条时间最短路径通往地点11，在这个城市交通网络中，有单向道，也有双向道，即如何处理一个有向图与无向图结合的图论问题，并且是一个两点间的最短路径问题： 图（一） 问题二阐述的是某公司员工往来于六个城市间，给出了这六个城市间的直达航班票价（表二），需要为这家公司提供出这六个城市间任意两点间的最小航班费用表 05040251050015202515010204020100102525201005510 2525550∞ ?? ??∞???? ∞∞?????? ∞?? ∞?? 表（二） 二、问题分析

图论最短路径问题 在消防选址中的应用 【摘 要】 最短路径问题是图论解决的典型实际问题之一，可用来解决管路铺设、线路 安装、厂区布局和设备更新等实际问题。介绍了图论最短路径问题及其算法，并应用图论最短路径问题的分析方法，解决城市消防站的选址问题。 【关键词】 最短路径；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 上的权。

最短路径问题（珍藏版） 【问题概述】最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结 点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查． 【十二个基本问题】 【问题 1】 作法 图形 原理 在直线 l 上求一点 P ，使 PA +PB 值最小． 连 AB ，与 l 交点即为 P ． 两点之间线段最短． PA +PB 最小值为 AB ． 【问题 2】“将军饮马” 作法 图形 原理 在直线 l 上求一点 P ，使 PA +PB 值最小． 作 B 关于 l 的对称点 B ＇ 连 A B ＇，与 l 交点即为 P ． 两点之间线段最短． PA +PB 最小值为 A B ＇． 【问题 3】 作法 图形 原理 在直线l 1 、l 2 上分别求点 M 、N ，使△PMN 的周长最小． 分别作点 P 关于两直线的 对称点 P ＇和 P ＇，连 P ＇P ＇与两直线交点即为 M ，N ． ， 两点之间线段最短． PM +MN +PN 的最小值为线段 P ＇P ＇＇的长． 【问题 4】 作法 图形 原理 在直线l 1 、l 2 上分别求点 M 、N ，使四边形 PQMN 的周长最小． 分别作点 Q 、P 关于直线 l 1 、l 2 的对称点 Q ＇和 P ＇ 连 Q ＇P ＇，与两直线交点即为 M ，N ． 两点之间线段最短． 四边形 PQMN 周长的最小值为线段 P ＇P ＇＇的长．

2020年中考数学专题突破专题十一：最短路径——造桥选址问 题

专题十一：最短路径——造桥选址问题 【导例引入】 导例：如图1，已知正方形ABCD 边长为3，点E 在AB 边上且BE=1，点P ，Q 分别是边BC ，CD 的动点（均不与顶点重合），当四边形AEPQ 的周长取最小值时，四边形AEPQ 的面积是 ． 【方法指引】 （1）如图，在直线l 上找M 、N 两点（M 在左），使得AM+MN+NB 最小，且MN=d 。 方法：将点A 向右平移d 个单位到A ′，作A ′关于直线l 的对称点A"，连接A"B 交直线l 于点N ，将点N 向左平移d 个单位到M ，点M 、N 即为所求，此时AM+MN+NB 最小为A"B 。 （2）如图，1l ∥2l ，1l ，2l 之间距离为d ，在1l ，2l 分别找M 、N 两点，使得MN ⊥1l ，且AM+MN+NB 最小。

l于点N，将点N向上平方法：将点A向下平移d个单位到A′，连接A′B交直线 2 移d个单位到M，点M，N即为所求，AM+MN+NB的最小值为A′B+d。 （3）如图，点P，Q在∠AOB内，分别在OA，OB上找点C，点D，使四边形PCDQ的周长最小. 方法：分别作P，Q关于OA，OB的对称点P′，Q′,连接P′Q′分别交OA，OB与点C，D，则此时四边形PCDQ的周长最小 本质为转化思想： （1）化同侧为异侧（对称变换）， （2）平移定距离（平移变换）， （3）化折线为直线（两点之间线段最短） “将军饮马”问题主要利用构造对称图形解决求两条线段和差、三角形周长、四边形周长等一类最值问题，会与直线、角、三角形、四边形、圆、抛物线等图形结合，在近年的中考和竞赛中经常出现，而且大多以压轴题的形式出现。【例题精讲】 类型一：两定点两动点形成最短路径型

初二数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题- 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题- 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题- 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．

在直线l 上求一点P ，使PB PA -的值最大． 作直线AB ，与直线l 的交 点即为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ． PB PA -的最大值＝AB ． 【问题11】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即为 P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ＇． PB PA -最大值＝AB ＇． 【问题12】“费马点” 作法 图形 原理 △ABC 中每一内角都小于120°，在△ABC 内求一点P ，使P A +PB +PC 值最小． 所求点为“费马点”，即满足∠APB ＝∠BPC ＝∠APC ＝120°．以AB 、AC 为边向外作等边△ABD 、△ACE ，连CD 、BE 相交于P ， 点P 即为所求． 两点之间线段最短． P A +PB +PC 最小值＝CD ． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有一 点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．3 B ．26 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 l B A l P A B l A B l B P A B' A B C P E D C B A A D E P B C

第11讲：轴对称 【问题概述】初中数学最值问题是每年中考必出题，更是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．一．【十二个基本问题】 在直线l上求一点 +PB 值最小。 【问题2】作图 在直线l上求一点 A+PB 值最小． 【问题3】“将军饮马”作图 在直线l1 、l2 上分别 求点M、N，使△PMN 周长最小． 【问题 4】作图 在直线l1、l2上分别求 M 、N ，使四 PQMN的周长最小。

直线m∥ n，在m、 上分别求点M、N，使 m，且AM+MN+BN 值最小。 【问题 6】作图 在直线l上求两点M、 在左），使MN a，并使 +MN+NB 的值最小 作图 l1上求点A，在l2 B，使P A+AB值最小． 【问题 8】作图 A 为l1上一定点，B 上；A 为l1上一定点， B 为l2上一定点，在 上求点M在l1上求点N 作图 在直线l上求一点 PA－的值最小 PB

二．“一次对称”常见模型:在直线 l 上求一点 PB PA －的值最大作图 在直线 l 上求一点 PB －的值最大 .【问题 12】“费马点”作图 ABC 中每一内角都小120°，在△ABC 内求一点P ，使 P A +PB +PC 最小．

选址问题数学模型 摘要 本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题 针对问题1：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall 算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。 针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。 针对问题3：建立了双目标最优化模型。首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8km、11km和12.5km，三组巡视的总路程达到35.3km，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2 。 关键词Floyd-Warshall算法穷举法最小生成树最短路径 1问题重述 1.1问题背景 这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社

13.4 课题学习最短路径问题 1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A，B分别是直线l异侧的两个点，在l上找一个点C，使CA＋CB最短，这时点C是直线l与AB的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求． 如图所示，点A，B分别是直线l同侧的两个点，在l上找一个点C，使CA＋CB最短，这时先作点B关于直线l的对称点B′，则点C是直线l与AB′的交点．

为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C′，连接AC′，BC′，B′C′，证明AC＋CB＜AC′＋C′B.如下：证明：由作图可知，点B和B′关于直线l对称， 所以直线l是线段BB′的垂直平分线． 因为点C与C′在直线l上， 所以BC＝B′C，BC′＝B′C′. 在△AB′C′中，AB′＜AC′＋B′C′， 所以AC＋B′C＜AC′＋B′C′， 所以AC＋BC＜AC′＋C′B. 【例1】在图中直线l上找到一点M，使它到A，B两点的距离和最小． 分析：先确定其中一个点关于直线l的对称点，然后连接对称点和另一个点，与直线l的交点M即为所求的点． 解：如图所示：(1)作点B关于直线l的对称点B′； (2)连接AB′交直线l于点M. (3)则点M即为所求的点．

点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题. 2.运用轴对称解决距离最短问题 运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同． 警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法．解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问． 3．利用平移确定最短路径选址 选址问题的关键是把各条线段转化到一条线段上．如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决．解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸

【图论基础】求一个无向图的最短路径（dijkstra） Time Limit:10000MS Memory Limit:65536K Total Submit:112 Accepted:46 Description 一个含n个结点的无向图，以矩阵存储方式给出，请求出指定的两个点之间的最短距离。 Input 第一行，一个整数n（0 < n < 1000 ），表示无向图中结点的个数。 接下来是一个n*n的矩阵，表示无向图中各结点之间的联结情况，矩阵中的数值为小于等于1000的下整数，其中0 表示两点之间无直接连接。 最后一行，两个整数i,j。表示求解i点到j点的最短距离。 Output 一个数值，表示指定的两点之间最短距离。 Sample Input 2 0 2 2 0 1 2 Sample Output 2 Source

?var ? i,j,k,n,min:longint; ? x,y:longint; ? a:array[1..1000,1..1000] of longint; ? b:array[1..1000] of longint; ? c:array[1..1000] of boolean; ?begin ? readln(n); ? for i:=1 to n do ? for j:=1 to n do read(a[i,j]); ? readln(x,y); ? fillchar(c,sizeof(c),0); ? fillchar(b,sizeof(b),$7); ? k:=x; b[x]:=0; ? for i:=1 to n-1 do begin ? c[k]:=true; ? for j:=1 to n do ? if (a[k,j]<>0) and not c[j] and (a[k,j]+b[k]

姓名：学号：专业：

图论的实际应用——蔬菜批发市场选址问题 摘要：在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，都可借助图论知识得以解决，而最短路问题是利用图论解决的一个典型的实际问题。图论中最典型的两种求最短路径的算法分别为Dijkstra算法和Floyd算法，其中Floyd算法广泛应用于求任意两点间的最短路径。本文介绍了利于Floyd算法来解决城市蔬菜批发市场选址的问题。 关键词：最短路；Floyd算法；选址问题 0．引言 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题[5]。在路径的优选计算问题中，最常见的是最短路径问题，最短路径可能是给定两点间的最短路径，也可能是任意各点间的最短路径。而在顶点的优选计算问题中，最为常见的是选址问题，所谓选址问题就是在某一地理区域构成的网络中选择一个顶点，建立服务设施，为该网络中的各个点提供服务，使得服务效率最高[3]。 选址问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。也可以是生产服务设施，如仓库，转运站等等。可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究[4]。尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。1．最短路径问题 最短路径问题是图论研究的一个经典算法问题，其目的是求出给定两点之间的长最短的路径，这里所说的长具有广泛意义，即可指普通意义的距离，也可是时间或费用等[2]。因此，最短路径问题通常可以归纳为三类：(1)距离意义上的最短路径，即求两点间距离最短的路径；(2)经济意义上的最短路径，即为两点间的费用最少的路径；(3)时间意义上的最短路径，即选择两点间最节省时间的

A B 最短路径问题专项练习 共13页，全面复习与联系最短路径问题 一、具体内容包括： 蚂蚁沿正方体、长方体、圆柱、圆锥外侧面吃食问题； 线段（之和）最短问题； 二、原理： 两点之间，线段最短；垂线段最短。（构建“对称模型”实现转化） 1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A，B分别是直线l异侧的两个点，在l上找一个点C，使CA＋CB最短，这时点C是直线l与AB的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求．如图所示，点A，B分别是直线l同侧的两个点，在l上找一个点C，使CA＋CB最短，这时先作点B关于直线l的对称点B′，则点C是直线l与AB′的交点． 为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C′，连接AC′，BC′，B′C′，证明AC＋CB＜AC′＋C′B.如下： 证明：由作图可知，点B和B′关于直线l对称， 所以直线l是线段BB′的垂直平分线． 因为点C与C′在直线l上， 所以BC＝B′C，BC′＝B′C′. 在△AB′C′中，AB′＜AC′＋B′C′， 所以AC＋B′C＜AC′＋B′C′， 所以AC＋BC＜AC′＋C′B. 【例1】在图中直线l上找到一点M，使它到A，B两点的距离和最小． 分析：先确定其中一个点关于直线l的对称点，然后连接对称点和另一个点，与直线l的交点M即为所求的点． 解：如图所示：(1)作点B关于直线l的对称点B′； (2)连接AB′交直线l于点M. (3)则点M即为所求的点． 点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题.

最短路问题及其应用 1 引言 图论是应用数学地一个分支，它地概念和结果来源非常广泛，最早起源于一些数学游戏地难题研究，如欧拉所解决地哥尼斯堡七桥问题，以及在民间广泛流传地一些游戏难题，如迷宫问题、博弈问题、棋盘上马地行走路线问题等．这些古老地难题，当时吸引了很多学者地注意．在这些问题研究地基础上又继续提出了著名地四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学地发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域地问题时，发挥出越来越大地作用．在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题地有力工具之一. 最短路问题是图论理论地一个经典问题.寻找最短路径就是在指定网络中两结点间找一条距离最小地路.最短路不仅仅指一般地理意义上地距离最短,还可以引申到其它地度量,如时间、费用、线路容量等. 最短路径算法地选择与实现是通道路线设计地基础,最短路径算法是计算机科学与地理信息科学等领域地研究热点,很多网络相关问题均可纳入最短路径问题地范畴之中.经典地图论与不断发展完善地计算机数据结构及算法地有效结合使得新地最短路径算法不断涌现. 2 最短路 2.1 最短路地定义 对最短路问题地研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()0 w≥地有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出地, ij 该算法能够解决两指定点间地最短路,也可以求解图G中一特定点到其它各顶点地最短路.后来海斯在Dijkstra算法地基础之上提出了海斯算法.但这两种算法都不能解决含有负权地图地最短路问题.因此由Ford提出了Ford算法,它能有效地解决含有负权地最短路问题.但在现实生活中,我们所遇到地问题大都不含负权,所以我们在()0 w≥地情况下选择Dijkstra算法. ij 定义①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e地权,则称这

课题学习《最短路径问题》教学设计 一、教学目标 让学生能够利用轴对称、平移变换解决简单的最短路径问题，体会图形的变化在解决最值问题中的作用，感悟转化思想． 二、教学重点及难点 重点：利用轴对称、平移等变换将最短路径问题转化为“两点之间，线段最短”问题．难点：如何利用轴对称、平移将最短路径问题转化为线段（或线段的和）最短问题． 三、教学用具 电脑、多媒体、课件、刻度尺、直尺 四、相关资源 微课，动画，图片. 五、教学过程 （一）引言导入 前面我们研究过一些关于“两点的所有连线中，线段最短”“连接直线外一点与直线上各点的所有线段中，垂线段最短”等的问题，我们称它们为最短路径问题．现实生活中经常涉及选择最短路径的问题，本节课我们将利用数学知识探究“将军饮马”和“造桥选址”两个极值问题． 设计意图：直接通过引言导入新课，让学生明确本节课所要探究的内容和方向． （二）探究新知 本图片是微课的首页截图，本微课资源由将军饮马的问题引出最短路径问题，并通过具体实例来巩固最短路径问题，有利于启发教师教学或学生预习或复习使用.若需使用，请插入微课【知识点解析】最短路径问题. 问题1如图，牧马人从A地出发，到一条笔直的河边l饮马，然后到B地．牧马人到河边的什么地方饮马，可使所走的路径最短？

1．将实际问题抽象为数学问题 学生尝试回答，并相互补充，最后达成共识． （1）把A，B两地抽象为两个点； （2）把河边l近似地看成一条直线，C为直线l上的一个动点，那么，上面的问题可以转化为：当点C在l的什么位置时，AC与CB的和最小． 2．解决数学问题 （1）由这个问题，我们可以联想到下面的问题：如图，点A，B分别是直线l异侧的两个点，如何在l上找到一个点，使得这个点到点A、点B的距离的和最短？ 利用已经学过的知识，可以很容易地解决上面的问题，即：连接AB，与直线l相交于一点C，根据“两点之间，线段最短”，可知这个交点C即为所求． （2）现在要解决的问题是：点A，B分别是直线l同侧的两个点，如何在l上找到一个点，使得这个点到点A、点B的距离和最短？ （3）如何能把点B移到l的另一侧B′处，同时对直线l上的任一点C，都保持CB与CB′的长度相等，就可以把问题转化为“上图”的情况，从而使问题得到解决． （4）你能利用轴对称的有关知识，找到符合条件的点B′吗？ 学生独立思考后，尝试画图，完成问题．小组交流，师生共同补充得出：

Dijstra 最短路径算法 1课程设计目的 为进一步巩固学习《数据通信与通信网技术》课程。加强对Dijstra最短路径算法的认识，所以需要通过实践巩固基础知识，为使我们取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。通过Dijstra 最短路径算法的设计和实现，达到进一步完善对通信网基础及应用课程学习的效果。增加对仿真软件的认识，学会对各种软件的操作和使用方法；加深理解路径算法的概念；初步掌握系统的设计方法，培养独立工作能力。 2设计方案论证 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 2.1 设计内容 沈阳大学

姓名： 令狐文艳 学号： 专业： 图论的实际应用——蔬菜批发市场选址问题 摘要：在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，都可借助图论知识得以解决，而最短路问题是利用图论解决的一个典型的实际问题。图论中最典型的两种求最短路径的算法分别为Dijkstra算法和Floyd算法，其中Floyd 算法广泛应用于求任意两点间的最短路径。本文介绍了利于Floyd算法来解决城市蔬菜批发市场选址的问题。 关键词：最短路；Floyd算法；选址问题 0．引言 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题[5]。在路径的优选计算问题中，最常见的是最短路径问题，最短路径可能是给定两点间的最短路径，也可能是任意各点间的最短路径。而在顶点的优选计算问题中，最为常见的是选址问题，所谓选址问题就是在某一地理区域构成的网络中选择一个顶点，建立服务设施，为该网络中的各个点提供服务，使得服务效率最高[3]。 选址问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。也可以是生产服务设施，如仓库，转运站等等。可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究[4]。尽管对选址的目标、要求有不

同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。 1．最短路径问题 最短路径问题是图论研究的一个经典算法问题，其目的是求出给定两点之间的长最短的路径，这里所说的长具有广泛意义，即可指普通意义的距离，也可是时间或费用等[2]。因此，最短路径问题通常可以归纳为三类：(1)距离意义上的最短路径，即求两点间距离最短的路径；(2)经济意义上的最短路径，即为两点间的费用最少的路径；(3)时间意义上的最短路径，即选择两点间最节省时间的路径。以上三类问题，都可以抽象为同一类问题，即带权图上的最短路径问题。不同意义下的距离都可以被抽象为网络图中边的权值，权值既可以代表“纯距离”，又可以代表“经济距离”，还可以代表“时间距离”。 1.1 Dijkstra算法 Dijkstra算法是一种求解最短路径方法。它是一个按路径长度递增的顺序产生最短路径的算法，其基本思想是：设图中所有顶点集合为V，另设置两个顶点集合S和T=V- S，集合S 中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点V1，然后不断从集合T中选取到顶点V1 的路径长度最短顶点Vi 加入到集合S中，集合S每加入一个新的顶点Vi，都要修改顶点V1到集合T中剩余顶点的最短路径长度值，此过程不断重复，直到集合T中的顶点全部加入到S中为止。这样，就可以求出一点到其它的任一顶点的最短路径。 Dijkstra算法简单易懂，在求给定两点间的最短距离时效率很高，但是其只能求图中一个特定结点到其他各个结点的最短路[1]。当需要求出图中任意两顶点的最短路径时，就需要以图中的每个顶点为起点，依次求出到另外顶点的最短路径，在