文档介绍：课程设计任务书 I
链路状态路由算法的实现 2
一、 问题描述 2
二、 基本要求 2
三、 设计思想 2
四、 系统结构 4
五、 程序流程（或模块划分） 5
六、 源程序 5
七、 测试数据 10
八、 测试情况 11据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由 算法是路由器的关键所在。为了完成这项工作，在路由器中保存着各种传输路径 的相关数据——路由表（Routing Table），供路由选择时使用，表中包含的信息 决定了数据转发的策略。打个比方，路由表就像我们平时使用的地图一样，标识 着各种路线，路由表中保存着子网的标志信息、网上路由器的个数和下一个路由 器的名字等内容。路由表可以是由系统管理员固定设置好的，也可以由系统动态 修改，可以由路由器自动调整，也可以由主机控制。
（三） Dijkstra 算法
按阶段进行，在每个阶段选择一个顶点V,它在所有unkown顶点中具有最 小的dv。阶段的其余部分由dw值的更新组成。
Dijkstra算法执行下列步骤：
1、 初始情况时，除了选择的顶点距离为0外，到其余所有顶点的距离dist都是 不可达的(INFINITY) o置所有的顶点known属性都是false„
2、 选择一个dist为最小的顶点V,将其known属性置为true。
3、 对每一个与顶点v邻接的顶点w,+cv,，更 。将w的经过的顶点置为V。
4、 重复2, 3,直到所有的顶点都被访问为止。
四、系统结构
int main()
主函数
void createGraph()拓扑图的创建
void printFileGraph()
存储矩阵到文件中
void initRoute()
实现路由表的复位
void Dijkstra()
Dijkstra算法求路径 void printRoute()
将路径表存到文件中
void deleteMemo()
释放所有动态空间
五、程序流程（或模块划分）
开始
插入节点数目
1
构造网络拓扑
1
保存拓扑到文件中
1
Dijkstra 算法
打印路由表
结束
六、源程序
IN C++
#include<iostream> 〃标准输入输出流头文件 #include<fstream> 〃文件输入输出头文件 #include<cstdlib> 〃防止编译 exit ()时出错 #include<iomanip> 〃因为使用了 setw ()语句 #include<> using namespace std; const int INFINITY^ 10000;
const int OK= 1;
const int updateTime=10;
void createGraph(int *arcs[],int & num)(
〃创建并初始化网络拓扑图
cout«"if输入路径的权值(用邻接矩阵表示拓扑图的方式):"«endl;
for (int i=0;i<num;i++)(
arcs[i]=new int [num];
for(int j=0;j<num;j++)
cin»arcs[i][j]; 〃输入对象到矩阵中
}
)
void printFileGraph(int *arcs[],int num){
〃把拓扑图中的邻接矩阵保存到文件中
ofstream outfile("",ios::out|ios::trunc);
if(! outfile)(
cout«H打开文件时出现错误!H«endl;
exit(l); 〃异常退出
}
outfile«H拓扑图的邻接矩阵n«endl;
for(int i=0;i<num;i++)
for(int j=O;j vnum;j++) (
outfile«setw(l 0)«arcs [i][j];
if((j+l)%num==0)
outfile«endl;
}
outfile«"注：n«endl;
outfile«INFINITY«H 表示无穷大 H«endl;
cout«"”vvendl;
();
void initRoute(int * R [],int RL[],int vNum)(
〃路由表数据复位
for(int i=0;ivvNum;i++){
RL[i]=INFNTY;
R[i]=new int[vNum];
for(int j=O;j<vNum;j++)
R[i]U]=-l；
}