图 论最短路问题实验目的实验内容
2、会用 Matlab软件求最短路
1、了解最短路的算法及其应用
1、图 论 的 基 本 概 念
2、最 短 路 问 题 及 其 算 法
3、最 短 路 的 应 用
4、建模案例：最优截断切割问题
5、实验作业图 论 的 基 本 概 念一,图 的 概 念
1、图的定义
2、顶点的次数
3、子图二,图 的 矩 阵 表 示
1,关联矩阵
2,邻接矩阵返回定义 有序三元组 G=(V,E,)称为一个 图,?
[ 1] V= },,,{
21 n
vvv? 是有穷非空集，称为 顶点集,
其中的元素叫图 G 的 顶点,
[ 2] E 称为 边集,其中的元素叫图 G 的 边,
[ 3]
是从边集 E 到顶点集 V 中的有序或无序的元素偶对的集合的映射，称为 关联函数,
例 1 设 G = ( V,E,? ),其中
V = { v
1
,v
2
,v
3
,v
4
},
E = { e
1
,e
2,
e
3
,e
4
,e
5
},
335414413312211
)(,)(,)(,)(,)( vvevvevvevvevve,
G 的图解如图,
图的定义定义 在图 G 中，与 V 中的有序偶 (v
i,v j ) 对应的边 e,称为图的 有向边 （或弧），而与 V 中顶点的无序偶 v i v j 相对应的边 e,称为图的 无向边,每一条边都是无向边的图，叫 无向图 ；每一条边都是有向边的图，称为 有向图 ；既有无向边又有有向边的图称为 混合图,
定义若将图 G 的每一条边 e 都对应一个实数 w (e ),称 w (e ) 为边的 权,
并称图 G 为 赋权图,
规定用记号? 和? 分别表示图的顶点数和边数,
常用术语：
（１） 端点相同的边称为 环,
（２） 若一对顶点之间有两条以上的边联结，则这些边称为 重边,
（３） 有边联结的两个顶点称为 相邻的顶点,有一个公共端点的边称为 相邻的边,
（４） 边和它的端点称为互相 关联 的,
（５） 既没有环也没有平行边的图，称为 简单图,
（６） 任意两顶点都相邻的简单图，称为 完备图,记为 K
n
，其中 n
为顶点的数目．
( 7) 若 V = X
Y,X
Y=
,X 中任两顶点不相邻,Y 中任两顶点不相邻，称 G 为 二元图 ；若 X 中每一顶点皆与 Y 中一切顶点相邻，称为 完备二元图,记为 K
m,n
，其中 m,n 分别为 X 与 Y 的顶点数目．
返回顶点的次数定义 （１）在无向图中，与顶点 v 关联的边的数目 （环算两次）
称为 v 的 次数,记为 d( v ),
（２）在有向图中，从顶点 v 引出的边的数目称为 v 的 出度,
记为 d + ( v ),从顶点 v 引入的边的数目称为的 入度,记为 d - ( v ),
d( v ) = d + ( v ) + d - ( v ) 称为 v 的次数．
4)( 4?vd
5)(
3)(
2)(
4
4
4
vd
vd
vd
定理１ )(2)(
)(
Gvd
GVv
推论１ 任何图中奇次顶点的总数必为偶数．
例 在一次聚会中，认识奇数个人的人数一定是偶数。
返回子图定义 设图 G = ( V,E,? ),G 1 = ( V 1,E 1,1? )
(1 ) 若 V 1? V,E 1? E,且当 e? E 1 时,1? (e)=? (e),则称 G 1 是 G 的 子图,
特别的，若 V 1 =V,则 G 1 称为 G 的 生成子图,
( 2 ) 设 V 1? V,且 V 1,以 V 1 为顶点集、两个端点都在 V 1 中的图 G 的边为边集的图 G 的子图，称为 G 的 由 V 1 导出的子图,记为 G [ V 1 ].
( 3 ) 设 E 1? E,且 E 1,以 E 1 为边集,E 1 的端点集为顶点集的图 G 的子图,
称为 G 的 由 E 1 导出的子图,记为 G [ E 1 ].
G G [ { v 1,v 4,v 5 }]G [ { e
1,e 2,e 3 }]
返回关联矩阵对无向图Ｇ，其关联矩阵Ｍ＝)( ijm,其中：
不关联与若相关联与若
ji
ji
ij ev
ev
m
0
1
M=
4
3
2
1
54321
10110
01100
01011
10001
v
v
v
v
eeeee
对有向图Ｇ，其关联矩阵Ｍ＝)( ijm,其中：
不关联与若的终点是若的起点是若
ji
ji
ji
ij
ev
ev
ev
m
0
1
1
注：假设图为简单图返回邻接矩阵对无向图Ｇ，其邻接矩阵 )( ijaA,其中：
不相邻与若相邻与若
ji
ji
ij vv
vv
a
0
1注：假设图为简单图
A=
4
3
2
1
4321
0111
1010
1101
1010
v
v
v
v
vvvv
对有向图Ｇ＝ （Ｖ，Ｅ），其邻接矩阵 )( ijaA,其中：
Evv
Evv
a
ji
ji
ij?
），若（
），若（
0
1
对有向赋权图Ｇ，其邻接矩阵 )( ijaA,其中：
Evv
ji
wEvvw
a
ji
ijjiij
ij
),(
0
,),(
若若为其权且若无向赋权图的邻接矩阵可类似定义．
A=
4
3
2
1
4321
0537
508
3802
720
v
v
v
v
vvvv
返回最 短 路 问 题 及 其 算 法一,基 本 概 念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路返回基 本 概 念通路 441125441
41
vevevevevW vv?
道路 43322645211
41
vevevevevevT vv?
路径 45211
41
vevevP vv?
定义１ 在无向图 G = ( V,E,? ) 中：
（１） 顶点与边相互交错且 iii vve 1)( ( i = 1,2,… k) 的有限非空序列
)(
12110 kkk
vevevevw
称为一条从
0
v 到
k
v 的 通路,记为
kvv
W
0
（２）边不重复但顶点可重复的通路称为 道路,记为
kvv
T
0
（３）边与顶点均不重复 的通路称为 路径,记为
kvv
P
0
定义２ （１）任意两点均有路径的图称为 连通图,
（２）起点与终点重合的路径称为 圈,
（３）连通而无圈的图称为 树,
定义３ （１）设 P( u,v ) 是赋权图 G 中从 u 到 v 的路径，
则称?
)(
)()(
PEe
ewPw 为路径 P 的 权,
( 2) 在赋权图 G 中，从顶点 u 到顶点 v 的具有最小权的路
),(
*
vuP,称为 u 到 v 的 最短路,
返回固 定 起 点 的 最 短 路最短路是一条路径，且最短路的任一段也是最短路．
假设在 u0-v0的最短路中只取一条，则从 u0到其余顶点的最短路将构成一棵以 u0为根的树．
因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．
Di j k s t r a 算法,求 G 中从顶点 u 0 到其余顶点的最短路设 G 为赋权有向图或无向图,G 边上的权均非负．
对每个顶点，定义两个标记 （ l v( ),z v( ) ），其中,
l v( ),表从顶点 u 0 到 v 的一条路的权．
z v( ),v 的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终 l v( ) 为从顶点
u 0 到 v 的最短路的权．
S,具有永久标号的顶点集输入,G 的带权邻接矩阵 ),( vuw
算法步骤：
（１）赋初值：令 S ＝ {u 0 },l u( )0 =0
v S V S\,令 l v( ) = W u v(,)0,z v( ) =u 0
u? u 0
（ 3 ） 设 v * 是使 l v( ) 取最小值的 S 中的顶点，则令 S = S ∪ {v * },
u? v *
（ 4 ） 若 S? φ,转 2,否则，停止,
用上述算法求出的 l v( ) 就是 u 0 到 v 的最短路的权，从 v 的父亲标记 )( vz 追溯到 u 0,就得到 u 0 到 v 的最短路的路线,
（ 2 ）更新 l v( ),z v( ),v S V S\,若 l v( ) > l u W u v( ) (,)?
则令 l v( ) = l u W u v( ) (,)?,z v( ) = u
例 求下图从顶点 u 1 到其余顶点的最短路．
先写出带权邻接矩阵,
0
30
640
930
2150
970
160
8120
W
因 G 是无向图，故 W 是对称阵．
TO MATLAB
(road1)
)(
i
ul迭代次数
1
u
2
u
3
u
4
u
5
u
6
u
7
u
8
u
１
2
3
4
5
6
7
8
０
0 ２ １ ８
2 8
10
8 3
10
8 6 10 12
7 10 12
9 12
1 2
最后标记,
)( vl
)( vz
0 2 1 7 3 6 9 12
1
u
1
u
1
u
6
u
2
u
5
u
4
u
5
u
)(
i
ul
1
u
2
u
3
u
4
u
5
u
6
u
7
u 8u
最后标记,
)( vl
)( vz
0 2 1 7 3 6 9 12
1u 1u 1u 6u 2u 5u 4u 5u
u1
u2
u3
u4
u5
u6
u7
u8
返回每 对 顶 点 之 间 的 最 短 路
( 二 ) 算法原理
1、求距离矩阵的方法
2、求路径矩阵的方法
3、查找最短路路径的方法
（一）算法的基本思想
（三）算法步骤返回算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出? 个矩阵 D ( 1 ),D ( 2 ),…,D (? ),使最后得到的矩阵 D (
)
成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径．
返回算法原理 —— 求距离矩阵的方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D ( 0 ) =)( )0(ijd =W
（１） D ( 1 ) =)( )1(ijd,其中 )0(1)0()1(,m i n { iijij ddd? })0(1 jd?
)1(
ijd 是从 v i 到 v j 的只允许以 v 1 作为中间点的路径中最短路的长度．
（ 2 ） D (2 ) =)( )2(ijd,其中 )1( 2)1()2(,m i n { iijij ddd? })1(2 jd?
)2(
ijd 是从 v i 到 v j 的只允许以 v 1,v 2 作为中间点的路径中最短路的长度．
…
（? ） D (? ) =
)(
)(
ijd,其中
)1()1()(,m i n {
iijij ddd }
)1(
jd
)(?
ijd 是从 v i 到 v j 的只允许以 v 1,v 2,…,?v 作为中间点的路径中最短路的长度．即是从 v i 到 v j 中间可插入任何顶点的路径中最短路的长，因此
D (? ) 即是距离矩阵,返回算法原理 —— 求路径矩阵的方法
R=)( ijr,r ij 的含义是从 v i 到 v j 的最短路要经过点号为 r ij 的点．
)( )0()0( ijrR,jr ij?)0(
每求得一个 D ( k ) 时，按下列方式产生相应的新的 R ( k )
否则若 )1()1()1(
)1(
)(
kkjkikkij
k
ij
k
ij
ddd
r
kr
在建立距离矩阵的同时可建立路径矩阵 R．
即当 vk被插入任何两点间的最短路径时，被记录在 R(k)中，依次求 时求得,可由 来查找任何点对之间最短路的路径．
)(?D )(?R )(?R
返回
i j
算法原理 —— 查找最短路路径的方法若 1)( pr ij,则点 p 1 是点 i 到点 j 的最短路的中间点,
然后用同样的方法再分头查找．若：
（１） 向点 i 追朔得,2)(
1
pr ip,3)(
2
pr ip,…,kip pr
k
)(?
（２） 向点 j 追朔得,1)(
1
qr jp,2)(
1
qr jq,…,jr jq
m
)(?
pk p2 p1p3 q1 q2 qm
则由点 i到 j的最短路的路径为,jqqqpppi
mk,,,,,,,,21,12
返回算法步骤
F l o y d 算法,求任意两点间的最短路．
D( i,j ),i 到 j 的距离．
R ( i,j ),i 到 j 之间的插入点．
输入,带权邻接矩阵 w ( i,j )
（１） 赋初值：
对所有 i,j,d ( i,j )? w( i,j ),r ( i,j )? j,k? 1
( 2 ) 更新 d( i,j ),r ( i,j )
对所有 i,j,若 d( i,k ) + d ( k,j ) < d ( i,j ),则 d( i,j )? d( i,k ) + d ( k,j ),r ( i,j )? k
( 3 ) 若 k =?,停止．否则 k? k + 1,转 （２）．
例 求下图中加权图的任意两点间的距离与路径．
TO MATLAB
(road2(floyd))
53334
34331
54324
33323
44441
,
06469
60243
42025
64207
93570
RD
951?d,故从 v 5 到 v 1 的最短路为９．
51r ＝４．
由 v 4 向 v 5 追朔,3,3 5354 rr ;
由 v 4 向 v 1 追朔,141?r
所以从 v 5 到 v 1 的最短路径为,1435,返回最 短 路 的 应 用一,可化为最短路问题的多阶段决策问题二,选 址 问 题
1,中心问题
2,重心问题返回可化为最短路问题的多阶段决策问题例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的,若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用,现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少,
已知该种设备在每年年初的价格为：
第一年 第二年 第三年 第四年 第五年
11 11 12 12 13
使用不同时间设备所需维修费为：
使用年限 0 － 1 1 － 2 2 － 3 3 － 4 4 － 5
维修费 5 6 8 11 18
构造加权有向图 G 1 ( V,E )
（ 1 ）顶点集 V ＝ { X ib,i =1,2,3,4,5 } ∪ { X ir k( ),i =2,3,4,5,6 ; k =1,2,…,i - 1 },
每个顶点代表年初的一种决策，其中顶点 X ib 代表第 i 年初购置新设备的决策，顶点 X ir k( ) 代表第 i 年初修理用过 k 年的旧设备的决策
（ 2 ）弧集 E = { (,),(,),
,
( )
,
X X X X
ib i b ir
k
i b1 1
i= 1,2,3,4; k= 1,2,…,i - 1}
∪ { (,)
,
( )
X X
ib i r? 1
1
,i = 1,2,3,4,5} ∪ { (,)
( )
,
( )
X X
ir
k
i r
k
1
1
,i= 1,2,3,4,5 ; k = 1,2,i - 1}
若第 i 年初作了决策 X
i
后，第 i + 1 年初可以作决策 X
i? 1
，则顶点 X
i
与
X
i? 1
之间有弧 ( X
i
,X
i? 1
),其权 W( X
i
,X
i? 1
) 代表第 i 年初到第 i + 1 年初之间的费用,例如，弧 (,)
( )
X X
b r3 4
1
代表第 3 年初买新设备，第四年初决定用第三年买的用过一年的旧设备，其权则为第三年初的购置费与三、四年间的维修费之和，为 12 ＋ 5 ＝ 17
（ 3 ）问题转化为顶点 X b1 到 X rk6( ) 的最短路问题,五年的最优购置费为
k
b r
kd X X
1 2 3 4 5
1 6
,,,,
( )m i n { (,)}
其中 d( X b1,X r
k
6
( )
) 为顶点 X b1 到 X r
k
6
( )
的最短路的权,
求得最短路的权为 53,而两条最短路分别为
X X X X X Xb r r b r r1 2
1
3
2
4 5
1
6
2( ) ( ) ( ) ( );
X X X X X Xb r b r r r1 2 1 3 4 1 5 2 6 3( ) ( ) ( ) ( )
因此，计划为第一、三年初购置新设备，或第一、四年初购置新设备，
五年费用均最省，为 53,
也可构造加权有向图 G 2 ( V,E ),
（ 1 ）顶点集 V = { V V V V V V1 2 3 4 5 6,,,,,},
V i 表第 i 年初购置新设备的决策,V 6
表第五年底,（ 2 ）弧集 E = { (,)V V
i j
,i = 1,2,3,4,5; i < j ≤ 6},
弧 (,)V V
i j
表第 i 年初购进一台设备一直使用到第 j 年初的决策，其权 W (,)V Vi j 表由这一决策在第 i 年初到第 j 年初的总费用，如
W
(,)V V
1 4 = 1 1+ 5+ 6+ 8= 30,
（ 3 ）问题转化为求 V 1 到 V 6 的最短路问题，求得两条最短路为 V V V1 4 6– –,V V V1 3 6– –
，权为 53,与图 G 1( V,E ) 的解相同．
返回
（ 2 ） 计算在各点
i
v 设立服务设施的最大服务距离 )(
i
vS,
}{m a x)(
1
ij
j
i
dvS
,2,1?i
选址问题 --中心问题例 2 某城市要建立一个消防站，为该市所属的七个区服务，
如图所示．问应设在那个区，才能使它至最远区的路径最短．
（ 1 ）用 F l oy d 算法求出距离矩阵 D=)( ijd,
（ 3 ）求出顶点 kv,使 )}({m i n)( 1 iik vSvS
则 kv 就是要求的建立消防站的地点．此点称为图的 中心点,
TO MATLAB
(road3(floyd))
05.15.55.8647
5.10475.45.25.5
5.5403247
5.87305710
65.425025
45.247203
75.5710530
D
S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,
S(v5)=7,S(v6)=7,S(v7)=8.5
S(v3)=6,故应将消防站设在 v3处。
返回选址问题 --重心问题例 3 某矿区有七个矿点，如图所示．已知各矿点每天的产矿量
)( jvq （标在图的各顶点上）．现要从这七个矿点选一个来建造矿厂．问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力
（千吨公里）最小．
（ 1 ）求距离阵 D=)( ijd,
（ 2 ） 计算各顶点作为选矿厂的总运力 )( ivm
ij
j
ji dvqvm
)()(
1
,2,1?i
（ 3 ） 求 kv 使 )}({m i n)(
1 iik
vmvm
,则 kv 就是选矿厂应设之矿点．此点称为图 G 的 重心 或 中位点,
返回实验作业生产策略问题,现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，
生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益。
某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为 a=6万单位，并以 b=1万单位 /月速度递增。若生产产品过剩，则需付单位产品单位时间（月）的库存保管费 C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费 C3=0.4元。假定生产率每调整一次带有固定的调整费
C1=1万元，试问工厂如何制定当年的生产策略，使工厂的总损失最小？
返回
2、会用 Matlab软件求最短路
1、了解最短路的算法及其应用
1、图 论 的 基 本 概 念
2、最 短 路 问 题 及 其 算 法
3、最 短 路 的 应 用
4、建模案例：最优截断切割问题
5、实验作业图 论 的 基 本 概 念一,图 的 概 念
1、图的定义
2、顶点的次数
3、子图二,图 的 矩 阵 表 示
1,关联矩阵
2,邻接矩阵返回定义 有序三元组 G=(V,E,)称为一个 图,?
[ 1] V= },,,{
21 n
vvv? 是有穷非空集，称为 顶点集,
其中的元素叫图 G 的 顶点,
[ 2] E 称为 边集,其中的元素叫图 G 的 边,
[ 3]
是从边集 E 到顶点集 V 中的有序或无序的元素偶对的集合的映射，称为 关联函数,
例 1 设 G = ( V,E,? ),其中
V = { v
1
,v
2
,v
3
,v
4
},
E = { e
1
,e
2,
e
3
,e
4
,e
5
},
335414413312211
)(,)(,)(,)(,)( vvevvevvevvevve,
G 的图解如图,
图的定义定义 在图 G 中，与 V 中的有序偶 (v
i,v j ) 对应的边 e,称为图的 有向边 （或弧），而与 V 中顶点的无序偶 v i v j 相对应的边 e,称为图的 无向边,每一条边都是无向边的图，叫 无向图 ；每一条边都是有向边的图，称为 有向图 ；既有无向边又有有向边的图称为 混合图,
定义若将图 G 的每一条边 e 都对应一个实数 w (e ),称 w (e ) 为边的 权,
并称图 G 为 赋权图,
规定用记号? 和? 分别表示图的顶点数和边数,
常用术语：
（１） 端点相同的边称为 环,
（２） 若一对顶点之间有两条以上的边联结，则这些边称为 重边,
（３） 有边联结的两个顶点称为 相邻的顶点,有一个公共端点的边称为 相邻的边,
（４） 边和它的端点称为互相 关联 的,
（５） 既没有环也没有平行边的图，称为 简单图,
（６） 任意两顶点都相邻的简单图，称为 完备图,记为 K
n
，其中 n
为顶点的数目．
( 7) 若 V = X
Y,X
Y=
,X 中任两顶点不相邻,Y 中任两顶点不相邻，称 G 为 二元图 ；若 X 中每一顶点皆与 Y 中一切顶点相邻，称为 完备二元图,记为 K
m,n
，其中 m,n 分别为 X 与 Y 的顶点数目．
返回顶点的次数定义 （１）在无向图中，与顶点 v 关联的边的数目 （环算两次）
称为 v 的 次数,记为 d( v ),
（２）在有向图中，从顶点 v 引出的边的数目称为 v 的 出度,
记为 d + ( v ),从顶点 v 引入的边的数目称为的 入度,记为 d - ( v ),
d( v ) = d + ( v ) + d - ( v ) 称为 v 的次数．
4)( 4?vd
5)(
3)(
2)(
4
4
4
vd
vd
vd
定理１ )(2)(
)(
Gvd
GVv
推论１ 任何图中奇次顶点的总数必为偶数．
例 在一次聚会中，认识奇数个人的人数一定是偶数。
返回子图定义 设图 G = ( V,E,? ),G 1 = ( V 1,E 1,1? )
(1 ) 若 V 1? V,E 1? E,且当 e? E 1 时,1? (e)=? (e),则称 G 1 是 G 的 子图,
特别的，若 V 1 =V,则 G 1 称为 G 的 生成子图,
( 2 ) 设 V 1? V,且 V 1,以 V 1 为顶点集、两个端点都在 V 1 中的图 G 的边为边集的图 G 的子图，称为 G 的 由 V 1 导出的子图,记为 G [ V 1 ].
( 3 ) 设 E 1? E,且 E 1,以 E 1 为边集,E 1 的端点集为顶点集的图 G 的子图,
称为 G 的 由 E 1 导出的子图,记为 G [ E 1 ].
G G [ { v 1,v 4,v 5 }]G [ { e
1,e 2,e 3 }]
返回关联矩阵对无向图Ｇ，其关联矩阵Ｍ＝)( ijm,其中：
不关联与若相关联与若
ji
ji
ij ev
ev
m
0
1
M=
4
3
2
1
54321
10110
01100
01011
10001
v
v
v
v
eeeee
对有向图Ｇ，其关联矩阵Ｍ＝)( ijm,其中：
不关联与若的终点是若的起点是若
ji
ji
ji
ij
ev
ev
ev
m
0
1
1
注：假设图为简单图返回邻接矩阵对无向图Ｇ，其邻接矩阵 )( ijaA,其中：
不相邻与若相邻与若
ji
ji
ij vv
vv
a
0
1注：假设图为简单图
A=
4
3
2
1
4321
0111
1010
1101
1010
v
v
v
v
vvvv
对有向图Ｇ＝ （Ｖ，Ｅ），其邻接矩阵 )( ijaA,其中：
Evv
Evv
a
ji
ji
ij?
），若（
），若（
0
1
对有向赋权图Ｇ，其邻接矩阵 )( ijaA,其中：
Evv
ji
wEvvw
a
ji
ijjiij
ij
),(
0
,),(
若若为其权且若无向赋权图的邻接矩阵可类似定义．
A=
4
3
2
1
4321
0537
508
3802
720
v
v
v
v
vvvv
返回最 短 路 问 题 及 其 算 法一,基 本 概 念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路返回基 本 概 念通路 441125441
41
vevevevevW vv?
道路 43322645211
41
vevevevevevT vv?
路径 45211
41
vevevP vv?
定义１ 在无向图 G = ( V,E,? ) 中：
（１） 顶点与边相互交错且 iii vve 1)( ( i = 1,2,… k) 的有限非空序列
)(
12110 kkk
vevevevw
称为一条从
0
v 到
k
v 的 通路,记为
kvv
W
0
（２）边不重复但顶点可重复的通路称为 道路,记为
kvv
T
0
（３）边与顶点均不重复 的通路称为 路径,记为
kvv
P
0
定义２ （１）任意两点均有路径的图称为 连通图,
（２）起点与终点重合的路径称为 圈,
（３）连通而无圈的图称为 树,
定义３ （１）设 P( u,v ) 是赋权图 G 中从 u 到 v 的路径，
则称?
)(
)()(
PEe
ewPw 为路径 P 的 权,
( 2) 在赋权图 G 中，从顶点 u 到顶点 v 的具有最小权的路
),(
*
vuP,称为 u 到 v 的 最短路,
返回固 定 起 点 的 最 短 路最短路是一条路径，且最短路的任一段也是最短路．
假设在 u0-v0的最短路中只取一条，则从 u0到其余顶点的最短路将构成一棵以 u0为根的树．
因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．
Di j k s t r a 算法,求 G 中从顶点 u 0 到其余顶点的最短路设 G 为赋权有向图或无向图,G 边上的权均非负．
对每个顶点，定义两个标记 （ l v( ),z v( ) ），其中,
l v( ),表从顶点 u 0 到 v 的一条路的权．
z v( ),v 的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终 l v( ) 为从顶点
u 0 到 v 的最短路的权．
S,具有永久标号的顶点集输入,G 的带权邻接矩阵 ),( vuw
算法步骤：
（１）赋初值：令 S ＝ {u 0 },l u( )0 =0
v S V S\,令 l v( ) = W u v(,)0,z v( ) =u 0
u? u 0
（ 3 ） 设 v * 是使 l v( ) 取最小值的 S 中的顶点，则令 S = S ∪ {v * },
u? v *
（ 4 ） 若 S? φ,转 2,否则，停止,
用上述算法求出的 l v( ) 就是 u 0 到 v 的最短路的权，从 v 的父亲标记 )( vz 追溯到 u 0,就得到 u 0 到 v 的最短路的路线,
（ 2 ）更新 l v( ),z v( ),v S V S\,若 l v( ) > l u W u v( ) (,)?
则令 l v( ) = l u W u v( ) (,)?,z v( ) = u
例 求下图从顶点 u 1 到其余顶点的最短路．
先写出带权邻接矩阵,
0
30
640
930
2150
970
160
8120
W
因 G 是无向图，故 W 是对称阵．
TO MATLAB
(road1)
)(
i
ul迭代次数
1
u
2
u
3
u
4
u
5
u
6
u
7
u
8
u
１
2
3
4
5
6
7
8
０
0 ２ １ ８
2 8
10
8 3
10
8 6 10 12
7 10 12
9 12
1 2
最后标记,
)( vl
)( vz
0 2 1 7 3 6 9 12
1
u
1
u
1
u
6
u
2
u
5
u
4
u
5
u
)(
i
ul
1
u
2
u
3
u
4
u
5
u
6
u
7
u 8u
最后标记,
)( vl
)( vz
0 2 1 7 3 6 9 12
1u 1u 1u 6u 2u 5u 4u 5u
u1
u2
u3
u4
u5
u6
u7
u8
返回每 对 顶 点 之 间 的 最 短 路
( 二 ) 算法原理
1、求距离矩阵的方法
2、求路径矩阵的方法
3、查找最短路路径的方法
（一）算法的基本思想
（三）算法步骤返回算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出? 个矩阵 D ( 1 ),D ( 2 ),…,D (? ),使最后得到的矩阵 D (
)
成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径．
返回算法原理 —— 求距离矩阵的方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D ( 0 ) =)( )0(ijd =W
（１） D ( 1 ) =)( )1(ijd,其中 )0(1)0()1(,m i n { iijij ddd? })0(1 jd?
)1(
ijd 是从 v i 到 v j 的只允许以 v 1 作为中间点的路径中最短路的长度．
（ 2 ） D (2 ) =)( )2(ijd,其中 )1( 2)1()2(,m i n { iijij ddd? })1(2 jd?
)2(
ijd 是从 v i 到 v j 的只允许以 v 1,v 2 作为中间点的路径中最短路的长度．
…
（? ） D (? ) =
)(
)(
ijd,其中
)1()1()(,m i n {
iijij ddd }
)1(
jd
)(?
ijd 是从 v i 到 v j 的只允许以 v 1,v 2,…,?v 作为中间点的路径中最短路的长度．即是从 v i 到 v j 中间可插入任何顶点的路径中最短路的长，因此
D (? ) 即是距离矩阵,返回算法原理 —— 求路径矩阵的方法
R=)( ijr,r ij 的含义是从 v i 到 v j 的最短路要经过点号为 r ij 的点．
)( )0()0( ijrR,jr ij?)0(
每求得一个 D ( k ) 时，按下列方式产生相应的新的 R ( k )
否则若 )1()1()1(
)1(
)(
kkjkikkij
k
ij
k
ij
ddd
r
kr
在建立距离矩阵的同时可建立路径矩阵 R．
即当 vk被插入任何两点间的最短路径时，被记录在 R(k)中，依次求 时求得,可由 来查找任何点对之间最短路的路径．
)(?D )(?R )(?R
返回
i j
算法原理 —— 查找最短路路径的方法若 1)( pr ij,则点 p 1 是点 i 到点 j 的最短路的中间点,
然后用同样的方法再分头查找．若：
（１） 向点 i 追朔得,2)(
1
pr ip,3)(
2
pr ip,…,kip pr
k
)(?
（２） 向点 j 追朔得,1)(
1
qr jp,2)(
1
qr jq,…,jr jq
m
)(?
pk p2 p1p3 q1 q2 qm
则由点 i到 j的最短路的路径为,jqqqpppi
mk,,,,,,,,21,12
返回算法步骤
F l o y d 算法,求任意两点间的最短路．
D( i,j ),i 到 j 的距离．
R ( i,j ),i 到 j 之间的插入点．
输入,带权邻接矩阵 w ( i,j )
（１） 赋初值：
对所有 i,j,d ( i,j )? w( i,j ),r ( i,j )? j,k? 1
( 2 ) 更新 d( i,j ),r ( i,j )
对所有 i,j,若 d( i,k ) + d ( k,j ) < d ( i,j ),则 d( i,j )? d( i,k ) + d ( k,j ),r ( i,j )? k
( 3 ) 若 k =?,停止．否则 k? k + 1,转 （２）．
例 求下图中加权图的任意两点间的距离与路径．
TO MATLAB
(road2(floyd))
53334
34331
54324
33323
44441
,
06469
60243
42025
64207
93570
RD
951?d,故从 v 5 到 v 1 的最短路为９．
51r ＝４．
由 v 4 向 v 5 追朔,3,3 5354 rr ;
由 v 4 向 v 1 追朔,141?r
所以从 v 5 到 v 1 的最短路径为,1435,返回最 短 路 的 应 用一,可化为最短路问题的多阶段决策问题二,选 址 问 题
1,中心问题
2,重心问题返回可化为最短路问题的多阶段决策问题例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的,若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用,现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少,
已知该种设备在每年年初的价格为：
第一年 第二年 第三年 第四年 第五年
11 11 12 12 13
使用不同时间设备所需维修费为：
使用年限 0 － 1 1 － 2 2 － 3 3 － 4 4 － 5
维修费 5 6 8 11 18
构造加权有向图 G 1 ( V,E )
（ 1 ）顶点集 V ＝ { X ib,i =1,2,3,4,5 } ∪ { X ir k( ),i =2,3,4,5,6 ; k =1,2,…,i - 1 },
每个顶点代表年初的一种决策，其中顶点 X ib 代表第 i 年初购置新设备的决策，顶点 X ir k( ) 代表第 i 年初修理用过 k 年的旧设备的决策
（ 2 ）弧集 E = { (,),(,),
,
( )
,
X X X X
ib i b ir
k
i b1 1
i= 1,2,3,4; k= 1,2,…,i - 1}
∪ { (,)
,
( )
X X
ib i r? 1
1
,i = 1,2,3,4,5} ∪ { (,)
( )
,
( )
X X
ir
k
i r
k
1
1
,i= 1,2,3,4,5 ; k = 1,2,i - 1}
若第 i 年初作了决策 X
i
后，第 i + 1 年初可以作决策 X
i? 1
，则顶点 X
i
与
X
i? 1
之间有弧 ( X
i
,X
i? 1
),其权 W( X
i
,X
i? 1
) 代表第 i 年初到第 i + 1 年初之间的费用,例如，弧 (,)
( )
X X
b r3 4
1
代表第 3 年初买新设备，第四年初决定用第三年买的用过一年的旧设备，其权则为第三年初的购置费与三、四年间的维修费之和，为 12 ＋ 5 ＝ 17
（ 3 ）问题转化为顶点 X b1 到 X rk6( ) 的最短路问题,五年的最优购置费为
k
b r
kd X X
1 2 3 4 5
1 6
,,,,
( )m i n { (,)}
其中 d( X b1,X r
k
6
( )
) 为顶点 X b1 到 X r
k
6
( )
的最短路的权,
求得最短路的权为 53,而两条最短路分别为
X X X X X Xb r r b r r1 2
1
3
2
4 5
1
6
2( ) ( ) ( ) ( );
X X X X X Xb r b r r r1 2 1 3 4 1 5 2 6 3( ) ( ) ( ) ( )
因此，计划为第一、三年初购置新设备，或第一、四年初购置新设备，
五年费用均最省，为 53,
也可构造加权有向图 G 2 ( V,E ),
（ 1 ）顶点集 V = { V V V V V V1 2 3 4 5 6,,,,,},
V i 表第 i 年初购置新设备的决策,V 6
表第五年底,（ 2 ）弧集 E = { (,)V V
i j
,i = 1,2,3,4,5; i < j ≤ 6},
弧 (,)V V
i j
表第 i 年初购进一台设备一直使用到第 j 年初的决策，其权 W (,)V Vi j 表由这一决策在第 i 年初到第 j 年初的总费用，如
W
(,)V V
1 4 = 1 1+ 5+ 6+ 8= 30,
（ 3 ）问题转化为求 V 1 到 V 6 的最短路问题，求得两条最短路为 V V V1 4 6– –,V V V1 3 6– –
，权为 53,与图 G 1( V,E ) 的解相同．
返回
（ 2 ） 计算在各点
i
v 设立服务设施的最大服务距离 )(
i
vS,
}{m a x)(
1
ij
j
i
dvS
,2,1?i
选址问题 --中心问题例 2 某城市要建立一个消防站，为该市所属的七个区服务，
如图所示．问应设在那个区，才能使它至最远区的路径最短．
（ 1 ）用 F l oy d 算法求出距离矩阵 D=)( ijd,
（ 3 ）求出顶点 kv,使 )}({m i n)( 1 iik vSvS
则 kv 就是要求的建立消防站的地点．此点称为图的 中心点,
TO MATLAB
(road3(floyd))
05.15.55.8647
5.10475.45.25.5
5.5403247
5.87305710
65.425025
45.247203
75.5710530
D
S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,
S(v5)=7,S(v6)=7,S(v7)=8.5
S(v3)=6,故应将消防站设在 v3处。
返回选址问题 --重心问题例 3 某矿区有七个矿点，如图所示．已知各矿点每天的产矿量
)( jvq （标在图的各顶点上）．现要从这七个矿点选一个来建造矿厂．问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力
（千吨公里）最小．
（ 1 ）求距离阵 D=)( ijd,
（ 2 ） 计算各顶点作为选矿厂的总运力 )( ivm
ij
j
ji dvqvm
)()(
1
,2,1?i
（ 3 ） 求 kv 使 )}({m i n)(
1 iik
vmvm
,则 kv 就是选矿厂应设之矿点．此点称为图 G 的 重心 或 中位点,
返回实验作业生产策略问题,现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率。生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会。可见，
生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益。
某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为 a=6万单位，并以 b=1万单位 /月速度递增。若生产产品过剩，则需付单位产品单位时间（月）的库存保管费 C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费 C3=0.4元。假定生产率每调整一次带有固定的调整费
C1=1万元，试问工厂如何制定当年的生产策略，使工厂的总损失最小？
返回
