Xidian Univ 集中式最短路径算法 讨论三种标准的集中式最短路径算法： -Bellman-Ford算法 Dijkstra算法 - Floyd-.Varshall算法。 Bellman-Ford算法和Dijkstra算法是点对多点的 最短路径算法 Floyd-Warshall算法则是多点对多点的最短路径 算法。 Broadband Wireless Communications Laboratory,Xidian University 6
Broadband Wireless Communications Laboratory, Xidian University 6 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 集中式最短路径算法 讨论三种标准的集中式最短路径算法： – Bellman-Ford算法 – Dijkstra算法 – Floyd-Warshall算法。 Bellman-Ford算法和Dijkstra算法是点对多点的 最短路径算法 Floyd-Warshall算法则是多点对多点的最短路径 算法
BW Xidia Bellman-Ford算法 典型的Bellman-Ford算法（简记为B-F算法)是 一种集中式的点到多点的路由算法，即寻找网络 中一个节点到其它所有节点的路由。 假定节点1是“目的节点”，我们要寻找网络中 其它所有的节点到目的节点1的最短路径。 ·用d,表示节点到节点的长度。 目的 8 节点 2 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 7 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 1． Bellman-Ford算法 典型的Bellman-Ford算法（简记为B-F算法）是 一种集中式的点到多点的路由算法，即寻找网络 中一个节点到其它所有节点的路由。 假定节点1是“目的节点”，我们要寻找网络中 其它所有的节点到目的节点1的最短路径。 用dij 表示节点i到节点j的长度。 1 2 3 4 5 目的 节点 1 1 4 2 2 2 8 4
BW Xidian Univ 定义：最短(sh)行走(Walk)是指在下列约 束条件下从给定节点到目的节点1的最短Wak。 ①该行走(Walk)中最多包括h条链路，即Walk中包 含的链路数至多为h条。 ②该行走(Walk)仅经过目的节点1一次。 最短（≤h)行走Walk长度用Dh表示。 对所有的h,令Dh=0。B-F算法的核心思想是通 过下面的公式进行迭代，即 D"=minld,+D] i≠1 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 8 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 定义：最短（ ）行走（Walk）是指在下列约 束条件下从给定节点i到目的节点1的最短Walk。 – ① 该行走（Walk）中最多包括h条链路，即Walk中包 含的链路数至多为h条。 – ② 该行走（Walk）仅经过目的节点1一次。 最短（ ）行走Walk长度用 表示。 对所有的h，令 。 B-F算法的核心思想是通 过下面的公式进行迭代，即 ≤ h ≤ h h Di 0 1 = h D 1 min[ ] 1 i h h ij j j D dD i + =+ ≠
Xidian Univ. 下面给出从h步Walk中寻找最短路由的算法。 第一步：初始化。即对所有ii≠1)令D=0。 第二步：对所有的节点)（)≠)，先找出使用一条链 路的最短(h≤l)的Walk长度； 第三步：对所有的节点)(j≠i)，再找出使用两条链 路的最短（h≤2)的Walk长度； 依次类推：如果对所有有：Dh=D-1(即继续迭代下去 以后不会再有变化)，则算法在次迭代后结束。 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 9 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 下面给出从h步Walk中寻找最短路由的算法。 – 第一步：初始化。即对所有i 令 。 – 第二步：对所有的节点j（ ），先找出使用一条链 路的最短（ ）的Walk长度； – 第三步：对所有的节点j（ ），再找出使用两条链 路的最短（ ）的Walk长度； – 依次类推：如果对所有i有： （即继续迭代下去 以后不会再有变化），则算法在h次迭代后结束。 = ∞ 0 Di (i ≠ 1) j ≠ i h ≤ 1 j ≠ i h ≤ 2 −1 = h i h Di D
目的 8 BW 节点 最短路径问题： 链路长度如图 Da=minld,+D] i≠ 中的标定所示 例5.2请 D=( 描述图5- D=∞ D D3=9 8中节点4 D=0 到节点1 的路由迭 D,=4 D=2 D=4 (b)最多使用1条链路的最短路径 (d)最多使用3条链路的最短路径 代过程。 D3=1D=9 D2=1D4 D4=0 02=0 D2=2 D2=6 D4=2 D=4 (c)最多使用2条链路的最短路径 (e)最终的最短路径 Broadband Wireless Communications Laboratory,Xidian University 10
Broadband Wireless Communications Laboratory, Xidian University 10 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 例5.2 请 描述图5- 8中节点4 到节点1 的路由迭 代过程。 1 2 3 4 5 目的 节点 1 1 4 2 2 2 8 4 最短路径问题： 链路长度如图 中的标定所示 1 1 D = 0 1 2 D = 1 1 3 D = 4 1 D4 = ∞ 1 D5 = ∞ （b）最多使用1条链路的最短路径 2 1 D = 0 2 2 D = 1 2 3 D = 2 2 4 D = 9 2 5 D = 6 （c）最多使用2条链路的最短路径 3 1 D = 0 3 2 D = 1 3 3 D = 2 3 4 D = 9 3 5 D = 4 （d）最多使用3条链路的最短路径 4 1 D = 0 4 2 D = 1 4 3 D = 2 4 4 D = 8 4 5 D = 4 （e）最终的最短路径 1 min[ ] 1 i h h ij j j D dD i + =+ ≠