过LS图计算。LS算法包含以下三个步骤。 ①各路由器主动测试所有与之相邻的路由器的状态,周期性地向相邻路由器发出 简短的查询报文,询问相邻路由器当前是否能够访问,假如对方作出反应,则说明链接 状态为UP,否则为DOwN。 ②各路由器周期性地向所有参与SPF的路由广播其LS信息,而不像VD算法那 样只向相邻路由器发送信息。 ③路由器收到LS报文后,利用它刷新网络拓扑图,将相应的连接状态改为UP 或DOWN。假如LS发生了变化,路由器立即利用 Dijkstra算法,这个算法可以求出 加权无向图中从某给定节点到目的节点的最小耗费路由或最佳路由。 Dijkstra算法是典型的最短路径算法,用于计算一个节点到其它所有节点的最短路 径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra算法能 得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 Dijkstra算法是已知整个网络拓扑和各链路的长度,寻找从源节点到网络中其它各 节点最短路径的算法。 Dijkstra算法如下。 方法:设某一节点为源节点,然后逐步寻找,每次找一个节点到源节节点的最短路 径,直至将所有的节点都找到为止。 步骤:令N表示所有网络节点的集合,M表示已由算法归并的节点的集合,C(n)为 源节点到节点n的距离,它是沿某一通路的所有链路的长度之和。len(,j为节点i至 之间的距离。 ①初始化 设节点1为源节点,先令M={}。对所有不在M中的节点n,写出 cl=lan)节点n与节点1直接相连 节点n与节点1不直接相连 ②寻找一个不在M中的节点w,其C(n)值为最小。把w加入到M中。然后对所 有不在M中的节点n,用[(n)C(w)+len(w,n中较小的值去更新原有的C(n)值,即 C(n):=Minc(n), c(w)+len(w, n)] ③重复步骤②,直到所有的网络节点都在M中为止。 例41某网络如图48所示,链路旁边注明的数字代表链路的长度。试利用 Dijkstra 算法求出从节点1到所有其它节点的最短路由。过 L-S 图计算。L-S 算法包含以下三个步骤。 ① 各路由器主动测试所有与之相邻的路由器的状态，周期性地向相邻路由器发出 简短的查询报文，询问相邻路由器当前是否能够访问，假如对方作出反应，则说明链接 状态为 UP，否则为 DOWN。 ② 各路由器周期性地向所有参与 SPF 的路由广播其 L-S 信息，而不像 V-D 算法那 样只向相邻路由器发送信息。 ③ 路由器收到 L-S 报文后，利用它刷新网络拓扑图，将相应的连接状态改为 UP 或 DOWN。假如 L-S 发生了变化，路由器立即利用 Dijkstra 算法，这个算法可以求出 加权无向图中从某给定节点到目的节点的最小耗费路由或最佳路由。 Dijkstra 算法是典型的最短路径算法，用于计算一个节点到其它所有节点的最短路 径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能 得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra 算法是已知整个网络拓扑和各链路的长度，寻找从源节点到网络中其它各 节点最短路径的算法。Dijkstra 算法如下。 方法：设某一节点为源节点，然后逐步寻找，每次找一个节点到源节节点的最短路 径，直至将所有的节点都找到为止。 步骤：令 N 表示所有网络节点的集合，M 表示已由算法归并的节点的集合，Cn为 源节点到节点 n 的距离，它是沿某一通路的所有链路的长度之和。len  i, j 为节点 i 至 j 之间的距离。 ① 初始化 设节点 1 为源节点，先令M  1。对所有不在 M 中的节点 n，写出          节点n与节点1不直接相连 len 1,n 节点n与节点1直接相连 C n ② 寻找一个不在 M 中的节点 w，其Cn值为最小。把 w 加入到 M 中。然后对所 有不在 M 中的节点 n，用  C   n ,C w  lenw,n 中较小的值去更新原有的C  n 值，即， C  n ：= Min  C  n ,Cw   len w,n 。 ③ 重复步骤②，直到所有的网络节点都在 M 中为止。 例 4.1 某网络如图 4.8 所示，链路旁边注明的数字代表链路的长度。试利用 Dijkstra 算法求出从节点 1 到所有其它节点的最短路由