Xidian Vniv. 5.3最短路由算法 通信工程学院信息科学研究所 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 1 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 5.3 最短路由算法 通信工程学院 信息科学研究所
Xidian Univ 最短路由 许多实际的路由算法都是基于最短路径这一概念。 这里首先要明确最短的含义，它取决于对链路长 度的定义。长度通常是一个正数，它可以是物理 距离的长短、时延的大小、各个节点队列长度等 等。如果长度取1，则最短路由即为最小跳数 (中转次数)的路由。其次，链路的长度随着时 间可能是变化的，它取决于链路拥塞情况。 最短路由算法的理论基础是图论。 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 2 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 最短路由 许多实际的路由算法都是基于最短路径这一概念。 这里首先要明确最短的含义，它取决于对链路长 度的定义。长度通常是一个正数，它可以是物理 距离的长短、时延的大小、各个节点队列长度等 等。如果长度取1，则最短路由即为最小跳数 （中转次数）的路由。其次，链路的长度随着时 间可能是变化的，它取决于链路拥塞情况。 最短路由算法的理论基础是图论
Xidian Univ. 图论复习 每一个网络都可以抽象成一个图。一个图G由一 个非空的节点集合N和节点间的链路A组成， 即G=(N,A) 0 链路可以是有方向的，也可以是无方向的。如果 节点和之间仅有i→j的链路，则称该链路是 有方向的（或单向链路)。如果节点和之间同 时有i→j及j→i的链路，则称该链路是无方 向的（或双向链路)。 方向图与无方向图 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 3 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 图 论 复 习 每一个网络都可以抽象成一个图。一个图G由一 个非空的节点集合N和节点间的链路A组成， 即 。 链路可以是有方向的，也可以是无方向的。如果 节点i和j之间仅有 的链路，则称该链路是 有方向的（或单向链路）。如果节点i和j之间同 时有 及 的链路，则称该链路是无方 向的（或双向链路）。 方向图与无方向图 G = (N, A) i → j i → j j → i
BW Xidian Univ 关联(Incident):它表示链路与节点的关系。 方向性行走(Walk)：是一个节点的序列，该 序列中关联的链路，是G中的一个链路。 方向性Path:指无重复节点的方向性Walk。 方向性环(Cycle):指开始节点和目的节点相 同的方向性Path。 强连通方向图：指对于每一对节点i,都有一条 方向性路径。 连通的方向图：指如果方向图对应的无方向图是 连通的，则该方向图是连通的。 Broadband Wireless Communications Laboratory,Xidian University
Broadband Wireless Communications Laboratory, Xidian University 4 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 关联（Incident）：它表示链路与节点的关系。 方向性行走（Walk）：是一个节点的序列，该 序列中关联的链路，是G中的一个链路。 方向性Path：指无重复节点的方向性Walk。 方向性环（Cycle）：指开始节点和目的节点相 同的方向性Path。 强连通方向图：指对于每一对节点i，j都有一条 方向性路径。 连通的方向图：指如果方向图对应的无方向图是 连通的，则该方向图是连通的
Xidian Univ. 给每条链路指定一个实数作为其长度，则一条方 向性路径p=(亿，j,k,l,m)的长度就是各链路长度之 和，即d+dk+…+dm。 最短路径问题就是寻找从到m的最小长度方向性 路径。 根据长度的不同定义，寻找最短路径的算法有不 同的含义。 Broadband Wireless Communications Laboratory,Xidian University 5
Broadband Wireless Communications Laboratory, Xidian University 5 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 给每条链路指定一个实数作为其长度，则一条方 向性路径 的长度就是各链路长度之 和，即 。 最短路径问题就是寻找从i到m的最小长度方向性 路径。 根据长度的不同定义，寻找最短路径的算法有不 同的含义。 p = (i, j,k,,l,m) dij + d jk ++ dlm
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 + =+ ≠