计算机网络实验原理实验八Link States Algorithm的实现.pdfVIP

计算机网络实验原理实验八LinkStatesAlgorithm的实现--第1页

云南大学软件学院

实验报告

实验八、LinkStatesAlgorithm的实现

1．实验目的：

通过编程模拟实现LSA.

2．实验环境：

VS.net软件开发平台，可以使用任何编程语言。

3．实验要求

（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。

（2）得到任何一个节点上的转发表。

4．实验分析，回答下列问题

（1）给出LSA算法的主要思想。

答：首先引进一个辅助向量D，其每个分量D[]表示当前阶段从起点start到顶点i所计算

出的最短路径。初始化之为：D[start]为0，其余D[]为“无穷大”。在每个阶段，该算法选

择所有顶点中D[]最小的未知顶点，将其标记为已知，然后对其所有的邻接顶点的D[]进行

更新(若新的D[]更小的话)，然后进入下一阶段，直至所有顶点均已知.

（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转

发表。

5.算法程序以及运行结果

代码如下：

#includestdio.h

#includestdlib.h

voidDijkstra(intn,intv,int*RoutWeight,int*Rout,int*MGraph[])

{

inti;

intj;

intmaxint=00000;//定义一个最大的数值，作为不相连的两个节点的代价权值

int*s;//定义具有最短路径的节点子集s

s=(int*)malloc(sizeof(int)*n);

//初始化最小路径代价和前一跳节点值

for(i=1;i=n;i++)

{

RoutWeight[i]=MGraph[v][i];//初始化V对应的的其余点的权重

s[i]=0;//现在该点不属于节点子集

if(RoutWeight[i]==maxint)//初始化会回溯路径

{

Rout[i]=0;

}

else

计算机网络实验原理实验八LinkStatesAlgorithm的实现--第1页

计算机网络实验原理实验八LinkStatesAlgorithm的实现--第2页

{

Rout[i]=v;

}

}

RoutWeight[v]=0;

s[v]=1;//源节点作为最初的s子集

for(i=1;in;i++)

{

inttemp=maxint