通信网理论基础(第三部分)Internet的地址路由和管理技术解析.ppt

* * Dijkstra算法说明： 节点1为源节点，L（i，j）为节点i至节点j之间的距离，D（v）为源节点至某节点v的距离，实际上它就是节点1沿某一路径到节点v的各链路长度之和。Dijkstra算法就是要求出D（v）的最短路径。基本方法是从源节点起，每次沿某一路径找出一个节点至源节点的最短路径，直到所有的点都找完为止。 * * （1）初始化：令N表示网络节点的集合。 N＝｛1｝，则对于所有N以外的节点，可以写出： D(v)＝l（1，v）； 若节点v与节点1直接相连； 或＝∞ ； 若节点v与节点1不直接相连； （2）有哪些信誉好的足球投注网站不在N中的节点w，要求D(w)最小。把w加入到N中；对所有不在N中的节点v，计算： D（v）←Min｛D（v）,D（w）＋L（w，v）｝；即取其中最小值更新原有的D（v）； （3）重复步骤2，直到所有的网络节点都在N中为止。 * * * * 计算：（下表，计算图E－1的网络的最短路径） 步骤 N D（2） D（3） D（4） D（5） D（6） 初始化 ｛1｝ 2 5 1 ∞ ∞ 1 ｛1，4｝ 2 4 ① 2 ∞ 2 ｛1，4，5｝ 2 3 1 ② 4 3 ｛1，2，4，5｝ ② 3 1 2 4 4 ｛1，2，3，4，5｝ 2 ③ 1 2 4 5 ｛1，2，3，4，5，6｝ 2 3 1 2 ④ * * * * Dijkstra算法的描述： N：网络中所有节点的集合； S：源节点； M：已由算法归并的节点的集合； Len（I，j）：节点i和j之间链路的权值，当I与j之间无连接时Len=∞； C（n）：算法求得当前从S到n的最小耗费路由的耗费； * * 算法： begin M :＝｛S｝； 若，节点n∈（N－S），则置C（n）:＝Len（S，n） S到n的最短距离:＝S到n路径；/* S与n直接相连时*/ do while M≠N 则，节点w∈（N－M），并且C（w）最小； M：＝M∪｛w｝; * * 若，节点n∈（N－M）； 置C（n）:＝Min（C（n），C（w）＋Len（w，n）） If （C（w）＋Len（w，n））?C（n）， 则，从S到n的最短路径:＝从S到W的最短路径加上从W到n的路径； end-if end-do end * * 端间最短径：Dijkstra 算法的另一种描述 指定端到其它端间的最短径算法： 端间的最短径具有普遍的意义。因为在实际的网络，例如计算机通信网络中，总是任意的两个端之间的通信。因此寻求端间的最佳路由－例如距离最短、时延最小、流量最大、成本最低、转接次数最少等路由就是最基本的选择。这些计算我们都以端间最短径表示。 * * 端间最短径：Dijkstra 算法的另一种描述 最基本的是研究指定端至其它端之间的最短径； 算法：迪克斯恰算法，即D算法。 指导思想：已知：给定图G，所有边的权dij，求指定端vs至其它端之间的最短径。 * * 端间最短径：Dijkstra 算法的另一种描述 D算法把端集分成两组： 一组称为置定端集Gp，另一组称为未置定端集G－Gp； 调整法就是在计算中，对于每个端都逐步的给予一个标值： * * 端间最短径：Dijkstra 算法的另一种描述 对于置定端，该标值就是求出的指定端vs到该端的最短径的长度； 对于未置定端，由于最短径尚未求出，所以暂时选择一个标值，但是这个标值是不断比较、优化、被调整的，该值将随着算法的进展而调整和优化。 * * 端间最短径：Dijkstra 算法的另一种描述 开始：令指定的端vs被置定，标值为0，此时，在置定端集中仅vs一个端；Gp＝｛Vs｝，而其它端均未置定；此时可标： wj＝dij（vij∈G－Gp）； 若：ds1＝Min dsj 即在未置定端集中选择距Vs端长度最短的一端V1，放入置定端集。因为这是V1与Vs之间最短径，G－Gp之间任何端至Vs，其长度均比它大。 记此时的标值：w1＝ds1； * * 端间最短径：Dijkstra 算法的另一种描述 下一步：选择第二个进入Gp的端，这时，该端可能有两种选择，一是直接与vs相连的vj端，长度记为wj＝dsj ； 一是通过V1转接的另外一端，（因为与其它端的最短径可能经v1转接），显然长度应该是该端至V1的距离d1j加上w1＝ds1所以： wi*＝min（wj，w1＋d1j）； * * 端间最短