云南大学软件学院计算机网络基础原理实验七.doc
.实验七、Link States Algorithm的实现序号： 姓名： 学号： 2016 成绩 1实验目的：通过编程模拟实现LSA.2实验环境：VS.net软件开发平台，可以使用任何编程语言。3实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。4.实验内容、拓扑结构ABDCE232111F2535通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。算法提示：Initialization: 2 N = u /*u is source node*/3 for all nodes j /* j is dest node*/4 if j adjacent to u 5 then D(j) = c(u,j) 6 else D(j) = 7 8 Loop 9 find i not in N such that D(i) is a minimum 10 add i to N 11 update D(j) for all j adjacent to i and not in N : 12 D(j) = min( D(j), D(i) + c(i,j) ) 13 /* new cost to j is either old cost to j or known 14 shortest path cost to i plus cost from i to j */ 15 until all nodes in N 4实验分析，回答下列问题（1）给出LSA算法的主要思想。LSA算法即链路状态选路算法，该算法中，网络拓扑和所有的链路费用都是已知的。它的具体实现依据Dijkstra算法，其主要思想是计算从某节点（源节点，u）到网络中所有其他节点的最短路径。其算法是迭代算法，即经算法的第k次迭代后，可知道到k个目的节点的最低费用路径，在在到所有目的节点的最低费用路径之中，这k条路径具有k个最低费用。（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。截图：转发表：A:目的地链路最低费用BA-B2CA-D-E-C3DA-D1EA-D-E2FA-D-E-F4B：目的地链路最低费用AB-A2CB-C3DB-D2EB-D-E3FB-D-E-F5C:目的地链路最低费用AC-E-D-A3BC-B3DC-E-D2EC-E1FC-E-F3D:目的地链路最低费用AD-A1BD-B2CD-E-C2ED-E1FD-E-F3E:目的地链路最低费用AE-D-A2BE-D-B3CE-C1DE-D1FE-F2F:目的地链路最低费用AF-E-D-A4BF-E-D-B5CF-E-C3DF-E-D3EF-E2源代码：#include#includeusing namespace std;const int MAX=1000;const int OK=1;const int FALSE=0;const int TRUE=1;void createGraph(int *arcs,int &num)cout请依次输入各点的各条路径的cost:endl(如果拓扑图中的顶点没有直接相连，则输入1000)endl;cout-endl;for (int i=0;inum;i+)arcsi=new int num;for(int j=0;jarcsij;void initRoute(int * R ,int RL,int vNum)for(int i=0;ivNum;i+)RLi=MAX;Ri=new intvNum;for(int j=0;jvNum;j+)Rij=-1;void updateRoute(int R1, int R2,int dest,int num)for(int i=0;inum;i+)R1i=R2i;for(int j=0;jnum;j+)if (R1j=-1)R1j=dest;break;void Dijkstra(int * arcs,int * R,int RL,int vexnum)char temp;int v0;bool * visit=new bool vexnum;couttemp;v0=(int)temp-65; /A的ASCII码是65cout=vexnum)cout输入错误，请重新输入v0;elsefor(int cnt=0;cntvexnum;cnt+)visitcnt=FALSE; /visit临时存储已经求得的最短路径RLcnt=arcsv0cnt;if(RLcntMAX)Rcnt0=v0;Rcnt1=cnt;RLv0=0;visitv0=TRUE;for(int i=1;ivexnum;i+)int min=MAX;int v=v0;for(int j=0;jvexnum;j+)if(!visitj)if(RLjmin)v=j;min=RLj;visitv=TRUE;for(int k=0;kvexnum;k+)if(!visitk&(min+arcsvkRLk)RLk=min+arcsvk;updateRoute(Rk,Rv,k,vexnum); visit=NULL;void printRoute(int * R,int RL, int vNum)int q=0;for(int dest=0;destvNum;dest+)if(RLdest!=0)printf(目标节点 :%c n,dest+65);if (Rdest0=-1)cout最短路径不存在!endl;continue;elsecout最低费用路径是:endl;for(int j=0;jvNum;j+)if(Rdestj!=-1)printf(%c,Rdestj+65);cout);elsebreak;cout最低费用:RLdestendl; cout*endl;int main()int vNum;coutvNum;while(vNum0)coutvNum;cout-endl;cout你输入的vNum个节点将按0-vNum-1顺序组成的邻接矩阵存储权值endl;int * weight=new int * vNum;int * shortestRoute=new int * vNum;int * routeLen=new int vNum;createGraph(weight,vNum);cout-endl;char isExit=y;doinitRoute(shortestRoute,routeLen,vNum);Dijkstra(weight,shortestRoute ,routeLen,vNum);printRoute(shortestRoute,routeLen,vNum);coutisExit;coutendl;if(isExit=n)break;while(isExit=y);return OK;
收藏
编号：2578776
类型：共享资源
大小：361.02KB
格式：DOC
上传时间：2020-04-21
8
金币
- 关 键 词：
-
云南大学
软件
学院
计算机网络
基础
原理
实验
试验
- 资源描述：
-
^.
实验七、Link States Algorithm的实现
序号： 姓名： 学号： 2016 成绩
1．实验目的：
通过编程模拟实现LSA.
2．实验环境：
VS.net软件开发平台，可以使用任何编程语言。
3．实验要求
（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。
（2）得到任何一个节点上的转发表。
4.实验内容、拓扑结构
A
B
D
C
E
2
3
2
1
1
1
F
2
5
3
5
通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。
算法提示：
Initialization:
2 N = {u} /*u is source node*/
3 for all nodes j /* j is dest node*/
4 if j adjacent to u
5 then D(j) = c(u,j)
6 else D(j) = ∞
7
8 Loop
9 find i not in N such that D(i) is a minimum
10 add i to N
11 update D(j) for all j adjacent to i and not in N :
12 D(j) = min( D(j), D(i) + c(i,j) )
13 /* new cost to j is either old cost to j or known
14 shortest path cost to i plus cost from i to j */
15 until all nodes in N
4．实验分析，回答下列问题
（1）给出LSA算法的主要思想。
LSA算法即链路状态选路算法，该算法中，网络拓扑和所有的链路费用都是已知的。它的具体实现依据Dijkstra算法，其主要思想是计算从某节点（源节点，u）到网络中所有其他节点的最短路径。其算法是迭代算法，即经算法的第k次迭代后，可知道到k个目的节点的最低费用路径，在在到所有目的节点的最低费用路径之中，这k条路径具有k个最低费用。
（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。
截图：
转发表：
A:
目的地
链路
最低费用
B
A->B
2
C
A->D->E->C
3
D
A->D
1
E
A->D->E
2
F
A->D->E->F
4
B：
目的地
链路
最低费用
A
B->A
2
C
B->C
3
D
B->D
2
E
B->D->E
3
F
B->D->E->F
5
C:
目的地
链路
最低费用
A
C->E->D->A
3
B
C->B
3
D
C->E->D
2
E
C->E
1
F
C->E->F
3
D:
目的地
链路
最低费用
A
D->A
1
B
D->B
2
C
D->E->C
2
E
D->E
1
F
D->E->F
3
E:
目的地
链路
最低费用
A
E->D->A
2
B
E->D->B
3
C
E->C
1
D
E->D
1
F
E->F
2
F:
目的地
链路
最低费用
A
F->E->D->A
4
B
F->E->D->B
5
C
F->E->C
3
D
F->E->D
3
E
F->E
2
源代码：
#include
#include
using namespace std;
const int MAX=1000;
const int OK=1;
const int FALSE=0;
const int TRUE=1;
void createGraph(int *arcs[],int &num)
{
cout<<"请依次输入各点的各条路径的cost:"<>arcs[i][j];
}
}
void initRoute(int * R [],int RL[],int vNum)
{
for(int i=0;i>temp;
v0=(int)temp-65; //A的ASCII码是65
cout<=vexnum)
{
cout<<"输入错误，请重新输入"<>v0;
}
else
{
for(int cnt=0;cnt");
}
else
break;
}
}
cout<<"最低费用:"<>vNum;
while(vNum<0)
{
cout<<"输入个数错误！请重新输入：";
cin>>vNum;
}
cout<<"---------------------------------------------------"<>isExit;
cout<
展开阅读全文
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
