最短路问讲义题应用

3 最短路问题的历史
渊源
最短路问题最早由荷兰 数学家 Edsger Dijkstra 在 1956 年提出。
最短路问题的定义
图论中的最短路问 题指什么？
在无向连通图或有向连通图 中，从某一起点到其余各顶 点的最短路径。
什么是路径长度？
路径长度是指路径上边或弧 的权值之和。
什么是无环图？
无环图指不存在环的图，可 以用拓扑排序求解最短路。
《最短路问题》PPT课件
欢迎来到最短路问题的世界。在本课件中，我们将介绍四种最短路算法及其 应用，并分析它们的优缺点。
问题背景
1 什么是最短路问题？ 2 为什么需要解决最
短路问题？
最短路问题是计算从源 节点到目标节点的最短 路径的问题。它是图论 中的一个经典算法问题。
很多实际问题都涉及到 最短路径的计算，比如 电网、交通、通信等领 域。
Floyd-Warshall算法解决的是所有点对之间 的最短路径问题，可以处理有向图或负边权 图。
Bellman-Ford算法
Bellman-Ford算法解决的是有向图中含有负 权边的单源最短路径问题。
A*算法
A*算法综合了贪心和广度优先搜索，在启发 函数的帮助下，可以高效解决带权图上的单 源最短路径问题。
算法示例
1
Step 1
假设我们要求从 A 点到其他各点的最
Step 2
2
短路径。
首先初始化 A 点到其他各点的距离为
无穷大，A 点到自身的距离为 0。
3
Step 3
找到 A 点的直接邻居，更新其距离值。
Step 4
4
重复 Step 3，直到所有节点的距离值 都已经更新。
总结

截断切割B题截断切割题目某些工业部门（如贵重石材加工等）采用截断切割的加工方式。

这里“截断切割”是指将物体沿某个切割平面分成两部分。

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长主体的对应表面是平行的）通常要经过6次截断切割。

设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。

（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数2、给出上述问题的数学模型和求解方法。

1、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。

2、对于e=0的情形有无简明的优化准则。

3、用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。

垂直切割费用为每平方厘米1元，r和e的数据有以下4组：a.r=1 e=0 ;b.r=1.5 e=0 ;c.r=8 ,e=0 ;d.r=1.5;2≤e≤15对最后一组数据应给出所有最优解，并进行讨论。

B题截断切割参考答案（1）需考虑的不同切割方式的总数V中共有6!=720个不同的元素，因此有720种不同的切割方式，注意到相继二次切割一对平行的平面时，交换这二次切割的先后次序不影响对应切割方式的费用，将费用相同的切割方式归成一类，每类取一种切割方式作不代表，此时仅需考虑加工费用可能不同的切割方式426种。

（2）问题归结为求一个定义在6个切割面排列次序的全体或它的一个子集上的函数的最小值。

目标函数应尽量用显式写出。

求解可用枚举法，分支定界法或其它方法，从尽可能简便有效作为评价标准：（3）一种作法如下：在直角坐标系中，表面平行于坐标平面的长方体可表示为{（x,y,z）,(a,b,c)},其中（x,y,z）为长方体某指定角点的坐标，a,b,c分别为它的长、宽、高。

二、最短路算法： 最短路算法：
1． D氏标号法（Dijkstra） 氏标号法（Dijkstra） （1）求解思路 求解思路——从始点出发，逐步顺序 从始点出发， 从始点出发 地向外探寻，每向外延伸一步都要求是最 地向外探寻，每向外延伸一步都要求是最 短的。 短的。 （2）使用条件 使用条件——网络中所有的弧权均 网络中所有的弧权均 非负， 非负，即 wij ≥ 0 。
（4） 计算步骤及例：
第三步：若网络图中已无T标号点 标号点， 第三步：若网络图中已无 标号点，停止 计算。否则 令 计算。否则,令
T ( v j0 ) =ຫໍສະໝຸດ min {T ( v )}
v j ∈s j
,
标号改成P 然后将 v j0 的T 标号改成 标号 ，转入第 二步。 二步。 此时，要注意将第二步中的 v1 改为 v j0 。 此时，
2 ,3, L , N ）
使用条件— 使用条件—没有负回路
3. 海斯算法
算法思想： 算法思想： 利用v 利用 vi 到 vj 的一步距离求出 vi 到 vj 的一步距离求出v 的两步距离, 的两步距离 , 再由两步距离求出四步 距离,经有限步迭代即可求得v 距离,经有限步迭代即可求得vi到vj的 最短路线和最短距离。 最短路线和最短距离。
6-2. 最 短 路 问 题
一、问题的提法及应用背景
（1）问题的提法 问题的提法——寻求网络中两点间 寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数为最小的通路。 注意： 总权数为最小的通路。（注意：在有向 图中，通路——开的初等链中所有的弧 开的初等链中所有的弧 图中，通路 开的初等链 应是首尾相连 首尾相连的 应是首尾相连的） （2）应用背景 应用背景——管道铺设、线路安排、 管道铺设、线路安排、 管道铺设 厂区布局、设备更新等。 厂区布局、设备更新等。

7.3
最短路问题
一、问题的提法及应用背景
（1）问题的提法——寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数为最小的通路。（注意：在有向 图中，通路——开的初等链中所有的弧 应是首尾相连的。） （2）应用背景——管道铺设、线路安排、 厂区布局、设备更新等。
二、最短路算法：
1． D氏标号法（Dijkstra）
(1)求解思路——从始点出发，逐步顺序地向
外探寻，每向外延伸一步都要求是最短的
(两层最小化的含义)。
(2)使用条件——网络中所有的弧权均非负，
即
w。 0 ij
(3)具体步骤 若用dij表示图中两相邻点i与j的距离，若i与j 不相邻，令dij=∞，显然dii=0，若用Lsi表示 从s点到i点的最短距离，现要求从s点到某一 点t的最短路，用Dijkstra算法的步骤如下： （1）从点s出发，因Lss=0，将此值标注在s 旁的小方框内，表示s点已标号；
6
2
v3
7
6
2
6ห้องสมุดไป่ตู้
5 0 v1 5 v2 7 2 7 v4
7 v5
6
1 2 v6
3 v7
2
v3
7 4
6
2
6
5 0 v1 5 v2 7 2 7 v4
7 v5
6
1 2 v6
3 v7
2
v3
7 4
6
10
2
6
反向追踪，得到最优路线：
v1
v3
v6
v5
v7，
最短路长L17=10.
作业
P225：
4，5；
算法思想示意图
ik
vk vn
v1

13.4 课题学习最短路径问题基础知识臺本技能1 .最短路径问题(1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求.如图所示，点A，B分别是直线I异侧的两个点，在I上找一个点C,使CA + CB最短，这时点C是直线I与AB的交点.(2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求.如图所示，点A, B分别是直线I同侧的两个点，在I上找一个点C,使CA + CB最短，这时先作点B关于直线I的对称点B'贝山点C是直线I与AB '的交点.B r为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C',连接AC',BC',B'C‘，证明AC+ CB V AC’t’B•如下：证明：由作图可知，点B和B'关于直线对称，所以直线I是线段BB'的垂直平分线.因为点C与C'在直线上，所以BC= B'C,BC'=B C.在△ABC '中,AB 'iAC'+C',所以AC+ B 'C<AC ' + C ',所以AC+ BC v AC ' -C B.【例1 ］在图中直线I上找到一点M ,使它到A, B两点的距离和最小.分析：先确定其中一个点关于直线I的对称点，然后连接对称点和另一个点，与直线I的交点M即为所求的点.解：如图所示：(1)作点B关于直线I的对称点B ';(2)连接AB '交直线于点M .(3)则点M即为所求的点.点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题.基本方法塘本縮力J JI IK M F .4 \ f® F A J P J扌K uV X !■? M E ■ J. J2.运用轴对称解决距离最短问题运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同.警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法.解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问.3.利用平移确定最短路径选址选址问题的关键是把各条线段转化到一条线段上.如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决.解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸的方法使河的宽度变为零，转化为求直线异侧的两点到直线上一点所连线段的和最小的问题.在解决最短路径问题时，我们通常利用轴对称、平移等变换把不在一条直线上的两条线段转化到一条直线上，从而作出最短路径的方法来解决问题.【例2］如图，小河边有两个村庄A, B,要在河边建一自来水厂向A 村与B村供水.E F(1)若要使厂部到A, B村的距离相等，贝S应选择在哪建厂？(2)若要使厂部到A, B两村的水管最短，应建在什么地方？分析：(1)到A, B两点距离相等，可联想到“线段垂直平分线上的点到线段两端点的距离相等”，又要在河边，所以作AB的垂直平分线，与EF的交点即为符合条件的点.(2)要使厂部到A村、B村的距离之和最短，可联想到“两点之间线段最短”，作A(或B)点关于EF的对称点，连接对称点与B点，与EF的交点即为所求.解：(1)如图1，取线段AB的中点G,过中点G画AB的垂线，交EF 于P,贝S P到A, B的距离相等.也可分别以A、B为圆心，1以大于2AB为半径画弧，两弧交于两点，过这两点作直线，与EF的交点P即为所求.⑵如图2,画出点A关于河岸EF的对称点A'，连接A'B交EF于P，则P到A, B的距离和最短.【例3】如图，从A地到B地经过一条小河（河岸平行），今欲在河上建一座与两岸垂直的桥，应如何选择桥的位置才能使从A地到B地的路程最短?思路导引：从A到B要走的路线是A—M —N —B,如图所示，而MN是定值，于是要使路程最短，只要AM + BN最短即可.此时两线段应在同一平行方向上，平移MN到AC,从C到B应是余下的路程，连接BC的线段即为最短的，此时不难说明点N即为建桥位置，MN即为所建的桥.解：（1）如图2，过点A作AC垂直于河岸，且使AC等于河宽.⑵连接BC与河岸的一边交于点N.（3）过点N作河岸的垂线交另一条河岸于点M •则MN为所建的桥的位置.思维拓展無斯应用K：Jl > / —- - *. . ........................................................................ .................. ~…• •--------------- ■ ■ ■ ....... ■■ ■: ■n iin 'ozi11 ：i n' i x i x Y I Yf i \ r;4 .生活中的距离最短问题由两点之间线段最短（或三角形两边之和大于第三边）可知，求距离之和最小问题，就是运用等量代换的方式，把几条线段的和想办法转化在一条线段上，从而解决这个问题，运用轴对称性质，能将两条线段通过类似于镜面反射的方式转化成一条线段，如图，AO + BO = AC的长.所以作已知点关于某直线的对称点是解决这类问题的基本方法.【例4】（实际应用题）茅坪民族中学八⑵班举行文艺晚会，桌子摆成如图a所示两直排（图中的AO, BO）, A0桌面上摆满了橘子, 0B桌面上摆满了糖果，站在C处的学生小明先拿橘子再拿糖果，然后到D处座位上，请你帮助他设计一条行走路线，使其所走的总路程最短？A---------- 0C・irB图a解：如图b.(1)作C点关于OA的对称点C i，作D点关于OB的对称点D i, ⑵连接C iD i，分别交OA, OB于P, Q,那么小明沿C-P-Q-D 的路线行走，所走的总路程最短.5.运用轴对称解决距离之差最大问题利用轴对称和三角形的三边关系是解决几何中的最大值问题的关键.先做出其中一点关于对称轴的对称点，然后连接对称点和另一个点，所得直线与对称轴的交点，即为所求.根据垂直平分线的性质和三角形中两边之差小于第三边易证明这就是最大值.破疑点解决距离的最值问题的关键运用轴对称变换及三角形三边关系是解决一些距离的最值问题的有效方法.【例5］如图所示，A, B两点在直线I的两侧，在I上找一点C,使点C到点A、B的距离之差最大.分析：此题的突破点是作点A（或B）关于直线I的对称点A'（或B）,Ci作直线A 'B（AB'）与直线I交于点C,把问题转化为三角形任意两边之差小于第三边来解决.解：如图所示，以直线I为对称轴，作点A关于直线I的对称点A',AB 的连线交I于点C,则点C即为所求.理由：在直线I上任找一点C（异于点C），连接CA, CA, CA',CB.因为点A, A'关于直线I对称，所以I为线段AA '的垂直平分线，则有CA= CA',所以CA—CB=CA ' -CB= A B.又因为点C'在上，所以C 'A = C 'A '•在8 ' BC '中,C 'A—C B= C A' -C B v A B,所以C 'A ' -C B v CA —CB.点拨：根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法.。

Step1：如果Si=V，算法终止，否则转入step2； Step2：考察每个使(vk,vj) ∈ A且vj不属于Si的点vj。如果T(vj)>P(vk)+wkj，则把T(vj) 修改为P(vk)+wkj，把 λ(vj)修改为k，否则转入step3；
Step3：令T(vji)=min{T(vj)| vj不属于Si}。如果T(vji)<+∞ ，则把vji的 T标号变为P标号，
令Si+1=Si ∪{vji}，k=ji，i=i+1，转入step1.
Matlab程序（见附件）
2 算法介绍-floyd算法

算法步骤：
Step1：输入图G的权矩阵W，对所有i，j，有dij=wij，k=1；
Step2：更新dij，对所有i，j，若dij>dik+dkj，则令dij=dik+dkj；
由此可以看出，算法的时间与随问题规模增大呈指数增长，所以最 短路算法不适合大规模配送问题求解。
考虑经过2点的Matlab程序（见附件）
3 应用举例
3.3 多目标运输问题
求次短路 Matlab程序
参考文献： 多目标最短路模型及算法，西南交通大学大学学报
最短路问题算法及应用
主要内容
1 问题描述 2 算法介绍
2.1 dijkstra算法 2.2 floyd算法
3 应用举例
3.1 物流中心选址 3.2 物流配送问题 3.3 多目标运输问题
1 问题描述
ቤተ መጻሕፍቲ ባይዱ
定义1 对简单图G的每一边e赋予一个实数，记为w(e)，称为边e的 权，而每边都赋予权的图称为赋权图。 定义2 (u,v)-路的边权之和称为该路的长，而u,v间路长达到最小的 路称顶点u和v的最短路。 在给定赋权图G中，求两个互异顶点间的最短路，简记为最短路问题。

定义: 给定一个赋权有向图，即给了一个有向图
G=（V，A，W） ，对每一个弧aij =(vi,vj)∈A ， 相应地有权w（aij ） =wij ∈V1 ，又给定 G中的 两个顶点vs ,vt 。设 P是G 中从vs 到 vt的一条路，
定义路 P的权是 P中所有弧的权之和，记为W(P)
。最短路问题就是要在所有从vs 到vt 的路中，求 一条权最小的路，即求一条从vs 到vt 的路P* ，
Thank You
在别人的演说中思考，在自己的故事里成长
Thinking In Other People‘S Speeches，Growing Up In Your Own Story
讲师：XXXXXX XX年XX月XX日
则resent= vk,
， 。 Sk Sk1 vk
Tk Tk1 vk
若k=n，则结束，否则转第二步。
6
例 用Dijkstra算法求前面例子中从v1到各点的最短路。
v2 1
6 2
v5
2
v9
6
3
v1
3 v3 6
3 4 10
1
2
v4
10
4
v6 2 v7
v8
7
图上标号法:
v2 v1,6 1
v5
v1, ∞ 2
转步骤二。
29
用逐次逼近算法求从V1到V6的最短路
v2
5
4
v1
-3
5
7
v3
v6 v4 6
2
v5
30
写在最后
经常不断地学习,你就什么都知道。你知道得越多,你就越有力量 Study Constantly, And You Will Know Everything. The More

5
0
5
V2
38
6 6 5 5 V6
V1 4
7 2
V4 7
1
6
8
V5 4
V3
V7
4
9
(7) 找出全部与v1,v2,v3,v4,v5,v6相邻旳未标识旳点v7， 求出从v1经过v5到这些点旳距离(v1->v2->v6->v5->v7:13) 以及经过v6到这些点旳距离(v1->v2->v6->v7:14)找出这些 距离中最短旳途径为v1->v2->v6->v5->v7，最短距离为 L15=13，将v7标识为13。至此全部点都已标识，即求出 了v1到全部其他点旳最短途径
5
5
0
5
V2
3
6 5 5 V6
V1 4
7 2
V4 7
1
6
8
V5 4
V3
V7
4
(4)找出全部与v1,v2,v3相邻旳未标识旳点v4,v5,v6，求出
从v1直接到这些点旳距离(v1->v4:7)以及经过v2到这些点 旳距离(v1->v2->v4:11;v1->v2->v5:10;v1->v2->v6:8)以及 经过v3到这些点旳距离(v1->v3->v4:6;v1->v3->v5:12)找出 这些距离中最短旳途径为v1->v3->v4，最短距离为L14=6， 将v4标识为6
数学模型
目的函数： P : min z
ij fij
(vi ,v j )A
fij 0或1, (vi , v j ) A
s.t.
fij f ji 1, i s

;
v1 16
59
30
41
22
23
v2 16 v3 17 v4 17 v5 18 v6
22 30
23 31
41
;
选址问题--中心问题
例 2 某 城 市 要 建 立 一 个 消 防 站 ， 为 该 市 所 属 的 七 个 区 服 务 ，
如 图 所 示 ． 问 应 设 在 那 个 区 ， 才 能 使 它 至 最 远 区 的 路 径 最 短 ．
数学模型与数学实验
图论模型
;
实验目的 实验内容
1、了解最短路的算法及其应用 2、会用Matlab软件求最短路
1、图 论 的 基 本 概 念
2、最 短 路 问 题 及 其 算 法
3、最 短 路 的 应 用 4、实验作业
;
固定起点的最短路
最短路是一条路径，且最短路的任一段也是最短路． 假设在u0-v0的最短路中只取一条，则从u0到其 余顶点的最短路将构成一棵以u0为根的树．
;
• if l(i)>l(j)+W(j,i) l(i)=l(j)+W(j,i); z(i)=j; if j<i i=j-1; end
end end i=i+1; end
;
floyd算法的基本思想
直接在图的带权邻接矩阵中用插入顶点的方法
依次构造出 个矩阵 D(1)、 D(2)、… 、D( )，使最 后得到的矩阵 D( )成为图的距离矩阵，同时也求出
插入点矩阵以便得到两点间的最短路径．
;
算法原理—— 求距离矩阵的方法
把带权邻接矩阵 W 作为距离矩阵的初值，即 D(0)= (di(j0) ) =W
（１）D(1)=
(di(j1) )

3
3,1
v3
0,0
6
1
2
10
v4
1,1
v5 6,2 2
∞,1
v9
6
3
3 4
10 4
v6 2 v7 ∞,1
11,4
∞,1
v8
18
v2 5,3 1
6 2
v1
3
3,1
v3
0,0
6
1
2
10
v4
1,1
v5 6,2 2
∞,1
v9
6
3
3 4
10 4
v6 2 v7 9,5
10,5
12,5
v8
19
v2 5,3 1
9
v2 6,1 1
6 2
v1
3
3,1
v3
0,0
6
1
2
10
v4
1,1
v5 ∞,1 2
6
3
4 10
4
v6
2
v7
∞,1
∞,1
∞,1
v9
3
∞,1
v8
10
v2 6,1 1
6 2
v1
3
3,1
v3
0,0
6
1
2
10
v4
1,1
v5 ∞,1 2
6
3
4 10
4
v6
2
v7
∞,1
∞,1
∞,1
v9
3
∞,1
v8
11
v2 6,1 1
6 2
v1
3
3,1
v3
0,0
6
1
2

最短路问题详解+题⽬概念若⽹络中的每条边都有⼀个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最⼩的路径就是最短路问题算法1. Floyd-warshall算法（1）介绍：⾮常的好⽤，通常可以在任何图中使⽤，包括有向图、带负权边的图。

（2）算法讲解：Floyd算法从第⼀个顶点开始，依次将每个顶点作为媒介k，然后对于每⼀对顶点u和v，查看其是否存在⼀条经过k的，距离⽐已知路径更短的路径，如果存在则更新它。

2. Dijkstra算法（1）介绍：是典型的单源最短路径算法，⽤于计算⼀个节点到其他所有节点的最短路径。

主要特点是以起始点为中⼼向外层层扩展，直到扩展到终点为⽌。

注意该算法要求图中不存在负权边。

（2）算法讲解：⽤贪⼼实现，先把起点到所有点的距离存下来找个最短的，进⾏松弛操作再找出最短的，把所有的点找遍之后就存下了起点到其他所有点的最短距离。

> 松弛操作：遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离> 注意：除了距离起点的距离为0外，其他距离均设为⽆穷⼤。

3. Bellman-Ford算法（1）介绍：Bellman-ford算法适⽤于单源最短路径，图中边的权重可为负数即负权边，但不可以出现负权环。

> 负权边：为负数的边。

> 负权环：源点到源点的⼀个环，环上权重和为负数。

（2）算法讲解：1.初始化：除了起点的距离为0外，其他均设为⽆穷⼤。

2.迭代求解：循环对边集合E的每条边进⾏松弛操作，使得顶点集合V中的每个顶点v的距离长逐步逼近最终等于其最短距离长；3.验证是否负权环：再对每条边进⾏松弛操作。

如果还能有⼀条边能进⾏松弛，那么就返回False，否则算法返回True题⽬输⼊:第⼀⾏n表⽰边的个数，接下来n⾏a,b,len，最后⼀⾏s，t求点s到点t的距离输⼊样例：71 2 22 5 21 3 42 3 13 5 61 4 73 4 1Dijkstra打法#include <bits/stdc++.h>#define maxx 0x7fusing namespace std;int u[105][105]={0x7f},dis[105];bool vis[105]={false};int main(){int n,s,t,x,y,minn,k;cin>>n;for (int i=1;i<=n;i++){dis[i]=maxx;vis[i]=false;}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)u[i][j]=maxx;for (int i=1;i<=n;i++){cin>>x>>y;cin>>u[x][y];}cin>>s>>t;for (int i=1;i<=n;i++)dis[i]=u[s][i];dis[s]=0;vis[s]=true;for (int i=1;i<=n;i++){minn=maxx;k=0;for (int j=1;j<=n;j++)if (vis[j]==false&&dis[j]<minn){minn=dis[j];k=j;}if (k==0) break;vis[k]=true;for (int j=1;j<=n;j++)if (dis[k]+u[k][j]<dis[j])dis[j]=dis[k]+u[k][j];}cout<<dis[t];return 0;}floyd打法#include <bits/stdc++.h>using namespace std;const int maxx=0x7f;int u[105][105];int main(){int s,t,n,x,y;cin>>n;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)u[i][j]=0x7f;for (int i=1;i<=n;i++){cin>>x>>y;cin>>u[x][y];}cin>>s>>t;for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (i!=j&&i!=k&&j!=k&&u[i][j]>u[i][k]+u[k][j])u[i][j]=u[i][k]+u[k][j];}cout<<u[s][t];return 0;}题⽬⼤意找⼀个点使得到其他点的距离总和最⼩Floyed穷举出答案#include <bits/stdc++.h>using namespace std;const int inf=100000007;int p[105],dis[105][105],sum;int n,lch,rch;int main(){cin>>n;memset(dis,inf,sizeof(dis));for(int i=1;i<=n;i++){dis[i][i]=0;cin>>p[i];cin>>lch>>rch;if(lch>=0) dis[i][lch]=1;dis[lch][i]=1;if(rch>=0) dis[i][rch]=1;dis[rch][i]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; int minn=inf;for(int i=1;i<=n;i++){sum=0;for(int j=1;j<=n;j++)sum+=p[j]*dis[i][j];if(minn>sum) minn=sum;}cout<<minn<<endl;return 0;}。

(1) 若 V1 V， E1 E,且当 e E1 时， 特 1 (e)= (e),则称 G1 是 G 的子图． 别的，若 V1=V，则 G1 称为 G 的生成子图．
(2)
设 V1 V，且 V1 ，以 V1 为顶点集、两个端点都在 V1 中的图 G 的边为边集的图 G 的子图，称为 G 的由 V1 导出的子图，记为 G[V1].
1 mij 1 0
若vi 是e j的起点 若vi 是e j的终点 若vi 与e j 不关联
邻接矩阵
对无向图Ｇ，其邻接矩阵 A (aij )nn ，其中：
1 aij 0
若vi 与v j 相邻 若vi 与v j 不相邻
注：假设图为简单图
v4 v1 v2 v 3 v 4
若vi 与e j 相关联 若vi 与e j 不关联
e1 1 M= 1 0 0
注：假设图为简单图
e2 e3 e4 e5 0 0 0 1 v1 1 0 1 0 v2 0 1 1 0 v3 1 1 0 1 v4
对有向图Ｇ，其关联矩阵Ｍ＝ (mij )nm ，其中：
公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从 其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任 意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路， 使得总成本最小？ 指派问题（assignment problem） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同， 不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总 回报最大？ 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线 （从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是 我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。

20 10
0
55
10
25
25 55
0
实验作业
生产策略问题：现代化生产过程中，生产部门面临的突出 问题之一，便是如何选取合理的生产率。生产率过高，导致 产品大量积压，使流动资金不能及时回笼；生产率过低，产 品不能满足市场需要，使生产部门失去获利的机会。可见， 生产部门在生产过程中必须时刻注意市场需求的变化，以便 适时调整生产率，获取最大收益。
作业
某公司在六个城市C1，…C6有分公司，从Ci到Cj 的直接航程票记在下述矩阵的（i,j）位置上。该公 司想要一张任两城市间的票价最便宜的路线表， 试作出这样的表格
0 50 40 25 10
50 0 15 20 25

15 0 10 20
40 20 10 0 10 25
25
0 3 5 10 7 5.5 7
3 0 2 7 4 2.5 4
5
2
0
5
2 4.5
6
D 10 7 5 0 3 7 8.5
7
4
2
3
0
4
5.5
5.5 2.5 4.5 7 4 0 1.5
7
4
6 8.5 5.5 1.5
0
(2) 计算在各点 vi 设立服务设施的最大服务 距离 S(vi)
解：(1) 用 Floyd 算法求出距离矩阵 D = (dij)vv： (2) 计算各顶点作为选矿厂的总运力 m(vi)
m (vi) q(vj)dij,i1,2, ,v j1
(3) 求 vk 使 m(vk)m 1i{im n(vi)}，则 vk 就是选矿厂应设 之矿点。此点称为图的重心或中位点。
选址问题2 现准备在 n 个居民点v1, v2, … , vn中设置一银 行.问设在哪个点,可使最大服务距离最小? 若设 置两个银行,问设在哪两个点?