北邮-通信网规划理论 第二章--电信网规划(二).docx

北邮-通信网规划理论 第二章--电信网规划(二)
北邮、通信网规划理论
通信网规划 通信网规划理论 网规划理论制作人：孙青华
北邮、通信网规划理论
其次章
电信网规划的根底学问
页









北邮、通信网规划理论
令始点Ts=0,并用框住，全部其它 始点T =0, 框住， 节点临时标记 Tj=∞ ; 启程， 从 vs 启程，对其相邻节点 vj1 进 行临时标记， 行临时标记，有 Tj1=ds,j1 ; 在全部临时标记中找出最小者， 在全部临时标记中找出最小者，并用 框住， 框住，设其为 vr是否全部节点都永久标记 是否全部节点都永久标记 N Y
Kruskal 算法： 算法： 计算两节点之 计算两节点之 间或一个节点到 全部节点之间的 最短路
算法完毕
启程， 从新的永久标记节点 vr 启程，对其相邻的临 时标记节点进展再标记，设 vj2 为其相邻节点 时标记节点进展再标记， ,那么 Tj2=min{Tj2, Tr+dr,j2 }
令 dij 表示 vi 到 vj 的干脆距 离(两点之间有 边),假设两点之 间没有边，那么 间没有边， 令 dij = ∞, 假设两点之间是 有向边， 有向边，那么 dji = ∞;令 dii = 表示始点， 0,s 表示始点， t 表示终点 8
北邮、通信网规划理论
例
狄克斯特拉算法 ∞ 10 ∞ 11
2 101










1 8 9 3 4∞ 12 15
5 20 2 2 30∞ t 31
s 8
15
4 ∞ 8
7
6∞ 13 15
每次迭代只有一个节点获得永久标记，假设有两个或两个以上节点的临时标记同 每次迭代只有一个节点获得永久标记， 每次迭代只有一个节点获得永久标记 9 时最小，可任选一个永久标记；总是从一个新的永久标记起先新一轮的临时标记， 时最小，可任选一个永久标记；总是从一个新的永久标记起先新一轮的临时标记， 是一种深探法 是一种深探法
北邮、通信网规划理论
Warshall-Floyd算法 Warshall-Floyd算法 (1962)
该算法基于根本的三角运算 =1,2,…, 执行三角运算， 定理 依次对 j=1,2, ,n 执行三角运算，那么 dik 间最短路的长度。 最终等于 i 到 k 间最短路的长度。
j dij i dik djk k
北邮、通信网规划理论










最短路问题的数学描述xij表示弧(i,j)是否位于s-t路上：当xij =1时，表示弧(i, 表示弧( 路上： =1时 表示弧( j)位于s-t路上，当xij =0时，表示弧(i,j)不在s-t路上. 路上， =0时 表示弧( 路上. 6min( i , j )∈ A
∑w x
5 (起先) A 起先) 4 7
B
D
6
ij ij
4 (完毕 完毕) F (完毕) 5 C 3 E 1
.
1, xij ∑ x ji = 1, ∑∈A j:( j ,i )∈A j:( i , j ) 0, xij ≥ 0.
i = s, i = t,
i ≠ s, t ,
思索： 思索： 关联矩阵是否必须是全么模矩阵？ 关联矩阵是否必须是全么模矩阵？
北邮、通信网规划理论
Bellman方程min
( i , j )∈ A