实验十六路由选择算法实验.doc

实验十六路由选择算法实验
【实验目的】
(1)熟悉网络层中典型的路由选择协议的原理设计方法。
(2)掌握OSPF算法,并将其用自己熟悉的语言实现算法。
【实验要求】
(1)在上机前有相应的成熟的算法,对自己程序的流程及源码有所准备;
(2)了解OSPF的适用网络;
【实验原理】
路由协议(Routing Protocol)是路由器之间实现路由信息共享的一种机制,它允许路由器之间相互交换和维护各自的路由表。当一台路由器的路由表由于某种原因发生变化时,它需要及时地将这一变化通知与之相连接的其他路由器,以保证数据的正确传递。路由协议不承担网络上终端用户之间的数据传输任务。
内部网关协议 IGP:具体的协议有多种,如 RIP 和 OSPF 等。
外部网关协议 EGP:目前使用的协议就是 BGP。
OPFS协议路由算法介绍
功能:寻找从某个源点到其余各顶点的最短路径
原理:按路径长度递增的顺序产生各个顶点的最短路径。
对于如图1所示的网络连接图,
引入一个距离向量D,它的每一个分量D[i]表示从源点v0到每个终点vi的最短路径长度。距离向量的初始值用下面方法确定:如果v1到终点vi有边,则D[i]为边长,否则D[i]为∞。
则图的初始距离向量为:D=[∞,2,5, 1,∞,∞]。如果已经找到了第一条最短路径(v1, vi)则下一个找到的最短路径是哪一条?
设该顶点的终点为vk(如何找到vk?)
则这条路径要么为(v1, vk),要么为(v1, vi, vk)
即找到最短路径长度D[i]后,更新剩下所有的最短路径长度
D[j]=Min((v1, vj), (v1, vi, vk)),最小的D[j]即为次短的最短路径。以此类推。
算法步骤描述如下:
1. 用邻接矩阵arcs表示有向图。S为找到最短路径的目标结点的集合,V为图中所有点的集合
2. 算法开始时S为空集,设出发点为v1 ,则辅助向量D的初始值为[∞,2,5, 1,∞,∞]
3. 选择vj ,使得D[i]=Min{D[k]|vk єV-S},则Vi就是当前找到最短路径的目标结点, 令S=S U {Vi}。
4. 修改从V1出发到集合V-S上任一点Vk的当前最短路径长度,如果
D[i]+arcs[i][k]<D[k], 则修改D[k]为D[k]= D[i]+arcs[i][k]
5. 重复3、4共n-1次(有向图有n个顶点)
【实验步骤】
#include""
#include""
#define MAXPOINT 3//定义最大的顶点数目
#define limit 32767 //设置没有路径的权代替无穷大
struct record{ //没个顶点的数据结构设置为一个数组队列
int number; //顶点号
int flag; //标志是否从队列中被选过如果为1表示选过为0表示未选
int allpath; //从源点到这个点的当前最短距离(权最小)
}path[MAXPOINT+1];
int cost[MAXPOINT+1][MAXPOINT+1]; //用来表示图的邻接矩阵
void main()
{int i,j,temp,front=1,rear=MAXPOI