- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
v j ( G G1 )
m in
( d ij ) d 1 2
*
得子图G2={v1, v2}.
8
P1：求G3
vi G 2 v j (G G 2 )
m in ( d ij ) d i 3
*
得子图 G3={ v1,v2,v3} ….. Pr-2 ：从Gr-1求Gr
v i G r 1 v j ( G G r 1 )
1
v2
v3
3
v4
算v4置定后的标值 w1*=min(w1, w4 +d41)=min(6,5+)=6 置定v1, 得vsv1的最短径w1=6
30
v1 vs
Vs V1 0 8 8 6 6 V2 V3 V4 4 2 6 3 5 5
8 4 2 1 3 3
v2
3
v3 置定 路由 v4 Vs 6 V3 Vs V3 V2 Vs V3 V2 V4 Vs V3 V4 V1 Vs V3 V2 V1
Dijkstra算法
v1 8 vs 2 4 v3 3 v2 1
24
直边不一定是最短径，如ds2 其实vs与v2间最短径长为3(经v3转接) 但可肯定,与vs相连的直边最小的一个必定 为最短径(如es3),其他转接至vs必不短. 算法从始找邻近端, 从vs 最邻近端找起， 每次得一个最短径。
v1 8 vs 2 4 v3 3 v2 1
D算法的适用条件
D算法可应用于有向图。 端点有权的处理策略。 如果边的权重有正有负，D算法不能应用于 这种情形。 Bellman-Ford（BF）算法
复杂度为O(n3)
33
2、所有端间最短径算法
Floyd算法（F算法）
给定图G及其边权dij(i,j=1,2,3,…n)
取矩阵W(0)（nn端端方阵）
D 1 i min d 1 i
v i G i
22
4.2.2 端间的最短径
基本问题：
网络结构已确定，寻找最短路由问题。
两种情况： 指定端至其它端最短径：Dijkstra算法。 任意二端间最短径：Floyd算法。
23
1、指定端至其它端最短径
已知 : G={V，E}及dij ，
求vs至其他端的最短径。
8 4 2 6 1 3 3
v2
3
v3
v4
28
8
v1
v2
vs
2
1
v3
3
v4
算v2置定后的标值 w1*=min(w1, w2 +d21)=min(8,3+3)=6 w4*=min(w4, w2 +d24)=min(5,3+3)=5
置定v4, 得vsv4的最短径w4=5 暂置w1=6
29
v1
vs
2
寻找最短主树是一个常见的优化问题。
4
一、问题描述
已知联结图G有n个端，以及相应的端间距离
d ij i , j 1, 2, , n
，若vi和vj之间没有边存在，可 以令距离为无穷大 ij ，目标是求最短主树， d 也即n-1条边的权和最小的联结子图。
5
二、最短主树的特征定理
W(0)=[ Wij(0)] 其元素：
Wij (0) dij eij E eij E 0 i j
34
nn
同时，有路由阵 R(0)=[ rij(0)]
nn
rij
(0)
j W ij 0
(0)
其它
35
初始化，即W(0),R(0)：只取直通路由，不考虑转接 以下依次取v1,v2,…vn做转接（无径的可有径，
原长径可能缩短）， 依次得：W
(1)，W (2)，…,W(n)
元素计算由W(k-1) W(k) (以vk为转接端)
wij(k)=min[wij(k-1),wik(k-1)+ wkj(k-1)]
路由阵:
ri j
(k )
k 若 w ij w ij ( k 1 ) (k ) ( k 1 ) ri j 若 w ij w ij
计算中的名词： 置定：某端置定即得到了至该端的最短径 标值：至该步时的暂时最短径（置定端可供转接） wi为vsvi的最短径长（vi已置定） wj*为vs vj的暂时的最短径长
25
D算法步骤
D1 开始置定vs，ws=0（vsvs），其他端 暂置wj=
D2
D3
置定vs的最邻近端，即min(dsj),算标值
把图中所有支撑树都列举出来，再按条件筛
选，选出符合条件的最短支撑树。这是一种 最直观又最繁杂的方法。可以得到最佳解， 但计算量往往很大。如n个端的全连通网， 其支撑树数目为n(n-2)个，已属于非多项式的 难题(NP Hard)。 穷举法只能用于端和边数较少的网络。
19
调整法
先选定适当的求最短支撑树的准则，如P算法 和K算法，但在每一步中要判断是否满足限制 条件，并进行调整，直至最后找出满足条件的 支撑树。 这类方法的复杂性一般都是多项式型的，但不 能保证取得最佳解，只能得到准最佳解，常用 的方法有E-W算法(厄斯威廉算法，EsouWillian算法)。它并不能保证最短性，但往往 相差不会太大，而其计算要比穷举法简单得多。
算v3置定后的标值(只计未置定端) w1*=min(w1, w3 +d31)=min(8,2+)=8 w2*=min(w2, w3 +d32)=min(4,2+1)=3 w4*=min(w4, w3 +d34)=min(6,2+3)=5 置定v2, 得最短径w2=3 暂置w1=8 w4=5
v1 vs
若T*是G的最短主树，则下述论断等价： （１）Ｔ*是Ｇ的最短主树 （２）对T*的任一连枝e，e是由e所决定的基本 圈中的最大权边。 （3）T*的任一树边e，e是由e决定的基本割集 中的最小权边。
本定理可以用于最短主树的搜索。
6
三、无限制条件的最短主树
无限制条件的最短主树的求法
顺序取端的Prim算法
(1) (2)
12
以vn回推,归纳法证:
a: vnvsn必共有, vnvsn< vnvsn’ b:若vr+1vsr+1为共有,则vrvsr必共有:
vr与vsr必有径
不用(vr,vsr)边,不经已共枝边,据(1),Q非最佳 若经已共枝边,则说明得到P树比Q树好
Prim算法是最佳算法.
13
算法复杂度分析
局间以及信道代价已知的情况下以最小的
费用规划联结的网络 通信网络拓扑结构确定后，怎样选择局站 间的最佳通信路由和备用路由，包括在转 接次数等指标符合一定要求的处理方法， 怎样选择站址和埋设管道的路由等
3
4.2.1 最短主树
联结图G本身不是树，则其主树可能不止 一个，但是满足特定条件的主树至少存在 一个。
m in
( d ij ) d ir
*
得子图 Gr={ v1,v2,…,vr} Pr-1 ：重复Pr-2,直至得到Gn为止
9
例：用Prim算法求如下图的最短主树。
v2
3 4 2 4
6 2 1 3 5
v7 v6 v5
10
v1
v3
v4
G1={v1} G2={v1,v3} G3={v1,v3,v6} G4={v1,v3,v6,v7} G5={v1,v3,v6,v7,v2} G6={v1,v3,v6,v7,v2,v5} G7={v1,v3,v6,v7,v2,v5,v4} 则w=15.
(k )
( k 1 )
36
j
k
j
k i i
w kj wij
wik
37
例: 用Floyd算法求下图中所有端间最短径。
v4
1.5 4
v1
0.5
2
v3
5
3.1
v7
15.6
v2
1.2
v5
9.2
6.7
v6
38
k=1
W
(0)
0 0 .5 2 1 .5
从算法始至终止,共进行n-1步。每步从k个端 与n-k个端比较,须经k(n-k)-1次得总计算量
[ k ( n k ) 1]
k 1
n 1
1 6
( n 1)( n 2 )( n 3)
约为n3量级,非NP-Hard问题,易于实现。
14
Kruskal算法(K算法)
特点：顺序取边。
16
破圈法
基本思想
从联结图中寻找圈，然后在圈中删去权最大
的边，最后剩下的无圈联结图为最短主树。
17
四、有限制条件的最短主树
有限制情况，例如站间通信时的转接次数不 宜过多，某条线路上的业务量不能太大等 存在两种解决问题的方法： 穷举法：逐个筛选主树 判断法：找主树过程中判断
18
穷举法
穷举法
20
Esau-William算法
已知为主机v1,dij,端业务量Fi 径边数K(限次转接) 径业务量M
v2
30
v3
10
3
4
12 3 2
40
0
v1
1
7
6
2
10
v4
5
v5
21
n端分为n个部分
每次取一边 部分数下降，至1终止
各部分之间算 tij=dij-D1i, D1i为第i部分与v1距离
倘若置定次序依次为, Vs,Vi , Vj ,…Vk则有 WsWi Wj …Wk
31
D算法计算量
