1.代码
#include<stdio.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<string.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<sys/timeb.h>
#include<stdarg.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAX_NAME 9//顶点名称字符串最大长度+1
#define INFINITY 1000//用1000代替∞
#define MAX_VERTEX_NUM 26 //最大顶点个数
typedef int Status;
typedef int Boolean;
typedef int VRType;//定义顶点关系类型为整型，与INFINITY的类型一致
typedef char PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//三维数组
typedef VRType DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组
typedef struct //边(弧)信息结构
{
VRType adj;//顶点关系类型，对带权图，表示权值
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组
enum GraphKind{DG,DN,UDG,UDN} ;//{有向图、无向网、无向图、无向网}
struct VertexType//最简单的顶点信息类型(只有顶点名称)
{
char name[MAX_NAME];//顶点名称
char routers[MAX_VERTEX_NUM][MAX_NAME];//定义最短路径中到目的节点的上一跳
} ;
struct MGraph//图的结构
{
VertexType vexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs;//邻接矩阵(二维数组)
int vexnum,arcnum;//图的当前顶点数和弧数
GraphKind kind; //图的种类标志
} ;
int stable=0;//到达稳定前路由表交换次数
void visit(VertexType ver)//访问顶点的函数
{
printf("%s",ver.name);
}
void input(VertexType &ver) //输入顶点信息的函数
{
scanf("%s",ver.name);
}
int LocateVex(MGraph G,VertexType u)
{
//查找顶点u,并返回其位置
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u.name,G.vexs[i].name)==0)
return i;
}
void CreateDN(MGraph &G)//构造有向网G
{
int i,j,k;
VRType w;//顶点关系类型
VertexType v1,v2;
printf(" 请输入网络拓扑结构中的节点数、弧数");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf(" 请输入%d个顶点的值（名称小于%d个字符）：",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;i++)//构造顶点向量
input(G.vexs[i]); //输入节点名称
for(i=0;i<G.vexnum;i++)//初始化二维邻接矩阵
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
}
printf(" 请输入%d条弧的弧尾 弧头 权值：\n",G.arcnum);
for(k=0;k<G.arcnum;k++)
{
scanf("%s %s %d",v1.name,v2.name,&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
}
VertexType GetVex(MGraph G,int v)
{
if(v>=G.vexnum||v<0)
exit(OVERFLOW);
return G.vexs[v];
}
void Display(MGraph G)
{
int i,j,k;
printf(" %d个顶点%d条弧的无向网。顶点依次是：",G.vexnum,G.arcnum);
for(i=0;i<G.vexnum;i++)
visit(GetVex(G,i));
printf("\n 初 始 路 由 表 如 下(1000表示无穷远):\n");
printf(" ");
for(i=0;i<G.vexnum;i++)
printf("%-8s",G.vexs[i].name);
printf("\n");
for(j=0;j<G.vexnum;j++)
{ printf("%20s",G.vexs[j].name);
for(k=0;k<G.vexnum;k++)
printf(" %-5d",G.arcs[j][k].adj);
printf("\n");
}
}
void ShortestPath_Floyd(MGraph G,PathMatrix P,DistancMatrix D)
{
//用Floyd算法随机更新两顶点间最短路径、顶点路由表，若P[v][w][u]为true，则u是从v到w当前求得最短路径上的顶点
int u,v,w,i,j,k;
int change=1;//路由表有无交换
int bad=1;//不好的交换
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
{
D[v][w]=G.arcs[v][w].adj;//顶点v到w的直接距离
for(u=0;u<G.vexnum;u++)
P[v][w][u]=FALSE;
if(D[v][w]<INFINITY)//从V到W有直接路径
{
strcpy(G.vexs[v].routers[w],G.vexs[v].name);
P[v][w][v]=P[v][w][w]=TRUE; //由v到w的路径经过v和w两点
}
else
strcpy(G.vexs[v].routers[w],"-");
}
srand((unsigned)time(NULL));//产生随机数种子，防止伪随机数
while(change==1)
{
for(;bad<20;)//连续20次随机交换无更新，为坏的交换，则停止随机交换
{
v=rand()%G.vexnum;
w=rand()%G.vexnum;
if(D[v][w]<INFINITY&&v!=w)
{
printf("%s节点向%s节点发送距离向量，",G.vexs[w].name,G.vexs[v].name);
change=0;
for(u=0;u<G.vexnum;u++)
{
if(D[w][u]<INFINITY&&D[v][w]+D[w][u]<D[v][u])//从v经u到w的一条路径更短
{
D[v][u]=D[v][w]+D[w][u];//更新最短距离
change=1;
bad=0; //一有更新，则不是坏的交换
if(w!=u)
strcpy(G.vexs[v].routers[u],G.vexs[w].name);//记录上一跳节点名称
for(i=0;i<G.vexnum;i++)
P[v][w][i]=P[v][u][i]||P[u][w][i];//从v到w的路径经过从v到u和从u到w的所有路径
}//if
}//for u
if(change==1)
{
stable++;
printf(" %s 的 路 由 表 如 下：\n",G.vexs[v].name);
printf(" 目的节点 最短路径 上一跳\n");
for(j=0;j<G.vexnum;j++)
printf(" %8s %8d %8s\n",G.vexs[j].name,D[v][j],G.vexs[v].routers[j]);
}// if change
else
{
printf(" %s 的 路 由 表 无更新：\n\n",G.vexs[v].name);
bad++;
}
}//if
}//for
}//while
printf("\n********************************************************************************\n");
printf(" 所以经过%d次交换，路由表达到稳定，最短路径矩阵为:\n",stable);
printf(" ");
for(i=0;i<G.vexnum;i++)
printf("%-8s",G.vexs[i].name);
printf("\n");
for(j=0;j<G.vexnum;j++)
{ printf("%20s",G.vexs[j].name);
for(k=0;k<G.vexnum;k++)
printf(" %-5d",D[j][k]);
printf("\n");
}
for(i=0;i<G.vexnum;i++)
{
printf(" %s 的 路 由 表 如 下：\n",G.vexs[i].name);
printf(" 目的节点 最短路径 上一跳\n");
for(j=0;j<G.vexnum;j++)
printf(" %8s %8d %8s\n",G.vexs[j].name,D[i][j],G.vexs[i].routers[j]);
}
}
main()
{
MGraph g;
int i,j,k;
PathMatrix p;
DistancMatrix d;
printf("***********************本程序完成距离向量路由算法的模拟*************************\n");
CreateDN(g);//构造有向网g
for(i=0;i<g.vexnum;i++)
g.arcs[i][i].adj=0;//顶点到自身距离为0
Display(g);//输出有向网g
ShortestPath_Floyd(g,p,d);//求每对顶点的最短路径
return 1;
} 2.运行结果
3.结果说明
首先通过输入得出各个路由顶点以及顶点之间的距离。然后打印出来。然后程序通过距离向量选路算法得出最小路径。最后打印出各个路由器之间的最短路径，“上一跳”表示在初始路由器和终点路由器之间，且和终点路由器直接相连的一个路由器节点。如果没有路径，上一跳由“-”表示。在运行结果中，我省略了一部分截图，里面表示“ 路 由 表 无更新“;