文档介绍：最短路由选择
实验报告
最短路径路由算法实现
实验报告
课 程 计算机网络
实验名称 最短路由选择
专业班级 信息 0803
姓 名 白乾涛
学 号 0909082401
实验日期
教师审批签字
二 零一零 年 十一月 二十 日
最短路径路由算法实现
一、实验目的和要求
<1>、实验目的
1、掌握最短路径路由算法的基本原理。
2、加强对最短路径算法的运用能力，能够采用一种编程语言实现最短路径路由算法。
<2>、实验要求
1、 对界面是否为图形化界面不做要求，但要能够满足相对应的输入输出条件。
2、 输入的起始节点 A 和目标节点 B 必须在拓扑图中，否则报错。
3、 拓扑图中的每一个路径的权值能够进行修改。
4、 在 A 到 B 不可达时，显示其不可达信息。
最短路径路由算法实现
二、实验关键数据结构及算法定义
<1>定义构造数据类型，存储结点名称和权值。
typedef struct ArCell
{
int adj; //路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
int name;
int num;
}infotype;
typedef struct
{
infotype vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph; MGraph b;
<2>以邻接矩阵存储图，同时实现了图的深度遍历
MGraph InitGraph(void)
{
MGraph G;
int i,j;
=6;
=6;
for(i=0;i<;i++)
[i].name=i;
for(i=0;i<;i++)
for(j=0;j<;j++)
[i][j].adj=INFINITY;
[0][1].adj=5;
[0][5].adj=1;
[1][2].adj=3;
[1][3].adj=4;
[2][3].adj=5;
[3][4].adj=4;
[4][5].adj=5;
[5][6].adj=INFINITY;
for(i=0;i<;i++)
for(j=0;j<;j++)
[j][i].adj=[i][j].adj;
最短路径路由算法实现
return G;
}
<3>弗洛伊德算法,通过图的权值矩阵求出任意两点间的最短路径。
void Floyd(MGraph *G)
{
int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vexnum;u++)
for(v=0;v<G->vexnum;v++)