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