文档介绍：中南大学
《计算机网络》实验报告
学生姓名
学号
专业班级
指导教师桂劲松
学院信息科学与工程学院
完成时间2011年1月
模拟路由算法的实现
一、实验内容
，演示每轮交换后路由表的变化。
。
二、实验目的及要求
本实验是计算机网络课程的实践性锻炼环节。通过实验，帮助学生更好地掌握网络通信协议的实现技术，锻炼学生应用高级编程语言完成通信编程的能力，使学生加深对网络协议本质的理解，巩固课堂所学的理论知识。要求实验者利用路由选择算法模拟软件提供的通信功能，模拟链路状态路由选择算法的初始化、路由信息扩散过程和路由计算方法；
掌握链路状态算法的路由信息扩散过程；
掌握链路状态算法的路由计算方法。
三、实验原理
编程语言： JAVA
编程工具： MyEclipse
实验实现方式：单机模拟实现
核心方法：dijkstra算法计算最短路径
分析：布置好各个模拟路由，以及路由的路程权值如何获取。
接着就是核心算法的实现，如何计算任意两个路由之间的最短路径问题。用到的是dijkstra算法。
Dijkstra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径，首先，它求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，一次类推，推而广之，再第i次迭代开始之前，算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。
这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一颗子树Ti，因为所有边的权值都是非负数，可以从与Ti的顶点相邻的顶点中找到下一个和起点最接近的顶点。和Ti的顶点相邻的顶点的集合称为“边缘顶点”，以他们为候选对象，Dijkstra算法可以从中选出一个最接近起点的顶点。为了确定第I个最接近的顶点，对于每一个边缘顶点u，该算法求出它到最近的树中顶点v的距离以及从起点到v得最短路径长度dv的和，再从中选出具有最小和的顶点。
开始
输入各个路由边的权值并计算运行
输出各个路由表信息。
各个路由分别运行一次dijkstra算法
结束
删除路由或继续测试？
此次实验主要是运用路由算法来处理路由当中的一些问题，利用Dijkstra算法处理最短路径的问题，在实验中这点已经得到了充分地体现。下面是该算法的流程图：
核心算法代码如下。
其中每个顶点用一个类来封装含有两个属性，一个是路由编号，一个是到某个路由的最短路径初始值为无限大。
void Dijkstra(int * arcs[],int * R[],int RL[],int vexnum){
//迪杰斯特拉算法
int v0; //定义源节点
bool * visit=new bool [vexnum];//已经确定最短路径的节点的集合
cout<<"请输入起始节点:";
cin>>v0;
cout<<endl;
for(int cnt=0;cnt<vexnum;cnt++){//进行主要的循环之前的初始化
visit[cnt]=FALSE;
RL[cnt]=arcs[v0][cnt];
if(RL[cnt]<INFINITY){
R[cnt][0]=v0;
R[cnt][1]=cnt;
}
} //for
RL[v0]=0;//源节点的标志
visit[v0]=TRUE; //初始化已经找到最短路径的点集合
for(int i=1;i<vexnum;i++){//dijkstra算法的主要循环
int min=INFINITY;
int v=v0;
for(int j=0;j<vexnum;j++)
if(!visit[j])
if(RL[j]<min){
v=j;
min=RL[j];
}
visit[v]=TRUE; //离v0顶点最近的v加入到s集
for(int k=0;k<vexnum;k++)//更新当前最短路径及距离
if(!visit[k]&&(min+arcs[v][k]<RL[k])){
//modify shortest r[j] and RL[j]
RL[k]=min+arcs[v][k];
updateRouteLen(R[k],R[v],k,vexnum);
}//if
}//for
delete[] vis