5 f
#define MAX NODES 1024 /* maximum number of nodes #define INFINITY 1000000000 /* a number larger than every maximum path * int n, dist[MAX-_[_NODES]: / dist(0] is the distance from i to i*/ void shortest-path(int s, int t, int path) struct state / the path being worked on * int predecessor; /* previous node * int length /* length from source to this node * enum (permanent, tentative) label /* label state * 3 state [MAX_NODES] int i, k, min struct state★ for(p = &state[o]: p<&state[n]: p++)[ / initialize state * p->predecessor =-1: p->length INFINITY state[t]. length= 0; state[t].label permanent k is the initial working node * do /* Is there a better path from k? * for(i= 0: i< n: i++) /* this graph has n nodes * if(dist([kJ[0l=0&& state[]. label = tentative)( if(state[k].length dist[kJ]< state[]. length)( state[O predecessor= k state[ length state[k].length +dist((k0: /* Find the tentatively labeled node with the smallest label. * k =O: min= INFINITY for (i=0; i< n: i++) if(state[O].label = tentative & state[0. length min)( min state0length k= i state[k].label permanent 1 while(k l= s); /* Copy the path into the output array. * 3 do path[i++]= k; k=state[k]. predecessor: while(k >=0) Fig. 5-7. Dijkstras algorithm to compute the shortest path through a graph
7.2路由算法(5) 7.23洪泛算法( Flooding) ■属于静态路由算法 基本思想 把收到的每一个包,向除了该包到来的线路外的所有输 出线路发送。 主要问题 洪泛要产生大量重复包。 ■解决措施 每个包头包含站点计数器,每经过一站计数器减1,为0 时则丢弃该包; 记录包经过的路径
7.2 路由算法（5） 7.2.3 洪泛算法（Flooding） ▪ 属于静态路由算法 ▪ 基本思想 - 把收到的每一个包，向除了该包到来的线路外的所有输 出线路发送。 ▪ 主要问题 - 洪泛要产生大量重复包。 ▪ 解决措施 - 每个包头包含站点计数器，每经过一站计数器减1，为0 时则丢弃该包； - 记录包经过的路径
7.2路由算法(6) 选择性洪泛算法( selective flooding) 洪泛法的一种改进。将进来的每个包仅发送到与正确方 向接近的线路上。 应用情况 路由器和线路的资源过于浪费,实际很少直接采用; -具有极好的健壮性,可用于军事应用 作为衡量标准评价其它路由算法
7.2 路由算法（6） ▪ 选择性洪泛算法（selective flooding） - 洪泛法的一种改进。将进来的每个包仅发送到与正确方 向接近的线路上。 ▪ 应用情况 - 路由器和线路的资源过于浪费，实际很少直接采用； - 具有极好的健壮性，可用于军事应用； - 作为衡量标准评价其它路由算法
7.2路由算法(7) 7.24基于流量的路由算法(FoW- Based Routing) 属于静态路由算法 基本思想 既考虑拓扑结构,又兼顾网络负荷; 前提:每对结点间平均数据流是相对稳定和可预测的: 根攝绛带和平均渡…耳得出均句惩迟因此路由选择 提前离线(of-ine)计算 需要预知的信息 网络拓扑结构; 通信量矩阵F 线路带宽矩阵Cⅱ; 路由算法(可能是临时的)
7.2 路由算法（7） 7.2.4 基于流量的路由算法（Flow-Based Routing） ▪ 属于静态路由算法 ▪ 基本思想 - 既考虑拓扑结构，又兼顾网络负荷； - 前提：每对结点间平均数据流是相对稳定和可预测的； - 根据网络带宽和平均流量，可得出平均包延迟，因此路由选择 问题归结为找产生网络最小延迟的路由选择算法。 - 提前离线（off-line）计算 ▪ 需要预知的信息 - 网络拓扑结构； - 通信量矩阵Fij； - 线路带宽矩阵Cij； - 路由算法（可能是临时的）