云南大学 软件学院 计网实验8
- 格式：doc
- 大小：44.00 KB
- 文档页数：5
云南大学软件学院
实 验 报 告
课程： 计算机网络原理实验 任课教师：
姓名： 学号： 专业： 成绩：
实验八、Link States Algorithm的实现
1．实验目的：
通过编程模拟实现LSA.
2．实验环境：
软件开发平台，可以使用任何编程语言。
3．实验要求
（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。
（2）得到任何一个节点上的转发表。
4.实验内容、拓扑结构
通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。
# include
# include
# define maxlen 10
# define large 999 //(该处设置路径最大值，表示不存在该路线)
typedef struct
{
int vexnum;
char vexs[maxlen];
int arcs[maxlen][maxlen];
}graph;
void init_graph(graph *g)//初始化图
{
int i = 0,j = 0;
g -> vexnum = 5; //根据题目此处将图的节点数初始化为5个
for(i = 0; i < 5; i++) //经过两层循环将条路径初始化为无穷大
for(j = 0; j < 5; j++)
g -> arcs[i][j] = 999;
g -> arcs[0][1] = 7; g -> arcs[1][0] = 7; //将相邻两个节点的路径初始化为其权值 7 1
8
1 2 2 g -> arcs[0][4] = 1; g -> arcs[4][0] = 1;
g -> arcs[1][2] = 1; g -> arcs[2][1] = 1;
g -> arcs[2][3] = 2; g -> arcs[3][2] = 2;
g -> arcs[1][4] = 8; g -> arcs[4][1] = 8;
g -> arcs[3][4] = 2; g -> arcs[4][3] = 2;
g -> vexs[0] = 'A'; //将节点值初始化
g -> vexs[1] = 'B';
g -> vexs[2] = 'C';
g -> vexs[3] = 'D';
g -> vexs[4] = 'E';
}
void shortpath_dijkstra(graph g)//寻找最短路径
{
int cost[maxlen][maxlen]; //cost[i][j]: 节点i到节点j的成本
int dist[maxlen]; //dist[i]: 源节点到i节点的距离或者是成本
int path[maxlen]; //已经经过了的节点
int s[maxlen]; //如果 s[i] = 1,那么i节点已经纳入最短路径集合
int i,j,v0,min,u;
char e;
printf("Input the source point(AorBorCorDorE):");//用户输入源节点
scanf("%c",&e);
switch(e)
{
case 'A':
v0=0;
break;
case 'B':
v0=1;
break;
case 'C':
v0=2;
break;
case 'D':
v0=3;
break;
case 'E':
v0=4;
break;
}
for(i = 0; i < g.vexnum; i++)
{
for(j = 0; j < g.vexnum; j++)
cost[i][j] = g.arcs[i][j];
} for(i = 0; i < g.vexnum; i++)
{
dist[i] = cost[v0][i]; //初始化源节点到各个节点的成本，如果与源节点相邻则成本为权值，否则为无穷大
if(dist[i] < large && dist[i] > 0)
path[i] = v0;
s[i] = 0;
}
s[v0] = 1;
for(i = 0; i < g.vexnum; i++)
{
min = large;
u = v0;
for(j = 0; j < g.vexnum; j++)
if(s[j] == 0 && dist[j] < min)
{
min = dist[j];
u = j;
}
s[u] = 1;
for(j = 0; j < g.vexnum; j++)
if(s[j] == 0 && dist[u] + cost[u][j] < dist[j])
{
dist[j] = dist[u] + cost[u][j];
path[j] = u;
}
}
printf("Output%c\n\n",e);
for(i = 0; i < g.vexnum; i++)
if(s[i] == 1)
{
u = i;
while(u != v0)
{
printf(" %c <- ",g.vexs[u]);
u = path[u];
}
printf(" %c ",g.vexs[u]);
printf(" :%d \n",dist[i]);
}
else printf(" %c <- %c: no path \n",g.vexs[i],g.vexs[v0]);
}
int main()
{ graph g;
init_graph(&g);
shortpath_dijkstra(g);
system("pause");
return 0;
}
从A点开始，寻找到其余各点的最短路径截图如下：
4．实验分析，回答下列问题
（1）给出LSA算法的主要思想。
1、路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。
2、路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
3、路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
4、如果这个节点不是V2（目的节点），路由器则返回到步骤5。
5、如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。
（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。
AB: A->E->D->C->B 最小成本为：6 AC: A->E->D->C 最小成本为：5
AD: A->E->D 最小成本为：3 AE: A->E 最小成本为：1
BD:B->C->D最小成本为：3 BC:B->C最小成本为1
BE:B->C->D->E最小成本为：5 CD:C->D 最小成本为：2
CE:C->D->E最小成本为：4 DE:D->E 最小成本为：2
（如果是源节点与目的节点反过来则路反过来即可）
各个节点的转发表：
A：
B:
C:
D: 目的地 链路
B （A,E）
C （A,E）
D （A,E）
E （A,E） 目的地 链路
A （B,C）
C （B,C）
D （B,C）
E （B,D）
目的地 链路
A （C,D）
B （C,B）
D （C,D）
E （C,D） 目的地 链路
A （D,E）
B （D,C）
C （D,C）
E （D,E） 目的地 链路
A （E,E）
B （E,D）
C （E,D） E: D （E,D）
