目录

前言

1 实验题目

2 实验目的

3 实验内容

3.1 步骤

3.2 关键代码

使用 Dijkstra 算法计算最短路径及输出节点的路由表

4 实验结果与分析

5 代码

---

前言

        本实验为计算机网络课程设计内容，基本上所有代码都是根据指导书给的附录写出来的。有些实验需要实现图形界面，但是出于期末考试压力，我所有实验均是在控制台输入输出的，没有花额外时间去学习qt了，有精力的同学可以自学一下qt实现简单的图形界面。同时，该博客内容为部分报告内容，仅为大家提供参考，请勿直接抄袭。另外，本次实验所用平台是dev c++5.11

1 实验题目

        实验四 OSPF 路由协议原型系统设计与实现

2 实验目的

        参考教材 OSPF 路由协议工作原理，在此基础上，实现一个简单的原型系统。主要完成工作有：路由节点泛洪发布本地节点的链路信息，其它节点接收信息，构造网络拓扑，然后利用 Dijkstra（或 Floyd）算法计算出到其它节点的最短路径，最后生成本节点的路由表。

3 实验内容

3.1 步骤

        （1）定义图的存储结构。

        （2）创建图的邻接矩阵表示法。

        （3）实现 Dijkstra 算法计算最短路径。

        （4）展示图的邻接矩阵。

3.2 关键代码

使用 Dijkstra 算法计算最短路径及输出节点的路由表

void shortDIJ(Graph g,int v0) {
	int i=0,v,w,Min,n=g.vexnum;
	int s[n],d[n],p[n];
	char temp[n];
	for(v=0; v<g.vexnum; v++) {
		s[v]=0;
		d[v]=g.arcs[v0][v];
		if(d[v]<Max)p[v]=v0;
		else p[v]=-1;
	}
	s[v0]=1;
	d[v0]=0;
	for(i=1; i<n; i++) {
		Min=Max;
		for(w=0; w<n; w++) {
			if(!s[w]&&d[w]<Min) {
				v=w;
				Min=d[w];
			}
		}
		s[v]=1;
		for(w=0; w<n; w++) {
			if(!s[w]&&d[v]+g.arcs[v][w]<d[w]) {
				d[w]=d[v]+g.arcs[v][w];
				p[w]=LocateVex(g, g.vexs[v]);
			}
		}
	}
	for(i=0; i<n; i++) {
		if(i!=v0&&d[i]<Max) {
			cout<<"从 "<<g.vexs[v0]<<" 到 "<<g.vexs[i]<<" 的最短路由为：";
			Min=0;
			for(w=p[i]; w!=v0; w=p[w]) {
				temp[Min++]=g.vexs[w];
			}
			cout<<g.vexs[v0];
			for(w=Min-1; w>=0; w--) {
				cout<<"->"<<temp[w];
			}
			cout<<"->"<<g.vexs[i];
			printf("%5c\t，代价为：%d",' ',d[i]);
			cout<<"\n";
		} else if(d[i]==Max) {
			cout<<-1<<" ";
		}
	}
	cout<<"节点 "<<g.vexs[v0]<<" 的路由表如下：\n";
	cout<<"---------\n";
	cout<<"|   "<<g.vexs[v0]<<"\t|\n";
	cout<<"---------\n";
	for(i=0; i<n; i++) {
		if(g.vexs[i]!=g.vexs[v0]) {
			cout<<"| "<<g.vexs[i]<<"->"<<d[i]<<"\t|\n";
		}
	}
	cout<<"---------\n";
}

4 实验结果与分析

（1）输入顶点数、边数和各条边的权重，创建出无向邻接矩阵。

图1.1 创建无向邻接矩阵

（2）输入某个路由器作为起点可以打印出它到其他路由器的最短路径、经过的路由器、代价和它的路由表。

图1.2 打印某个起点的最短路径和路由表

5 代码

#include <iostream>
#include <iomanip>
using namespace std;

//#define Max 1e6
//#define MVNum 100         //最大顶点数
//#define OK 1

const int Max = 1e5;		//最大权重
const int MVNum = 1e2;		//最大顶点数
const int OK = 1;

const int mm = 1e2;

typedef char VerTexType;	//顶点信息
typedef int OtherInfo;    	//和边相关的信息
typedef int ArcType;		//边的类型

//- - - - -图的邻接表存储表示- - - - -
typedef struct {
	int info;
	VerTexType vexs[MVNum];			//顶点表
	ArcType arcs[MVNum][MVNum];		//邻接矩阵
	int vexnum, arcnum;        		//图的当前点数和边数
} Graph;

//确定顶点v在G中的位置
int LocateVex(const Graph &g, VerTexType v) {
	for(int i = 0; i < g.vexnum; ++i)
		if(g.vexs[i] == v)
			return i;
	return -1;
}//LocateVex


void CreateGraph(Graph &g) {
	//采用邻接矩阵表示法，创建无向图G
	/****在此下面完成代码***************/
	int i,j,k,w;
	char v1,v2;
	cout<<"请输入顶点数：";
	cin>>g.vexnum;
	while(g.vexnum==0) {
		cin.clear();
		cin.sync(); //清空缓冲区
		cout<<"输入错误请重新输入：";
		cin>>g.vexnum;
	}
	cout<<"请输入边数：";
	cin>>g.arcnum;
	while(g.arcnum==0) {
		cin.clear();
		cin.sync(); //清空缓冲区
		cout<<"输入错误请重新输入：";
		cin>>g.arcnum;
	}

	cout<<"请输入"<<g.vexnum<<"个顶点的名称：";
	for(i=0; i<g.vexnum; i++) {
		cin>>g.vexs[i];
	}
	for(i=0; i<g.vexnum; i++) {
		for(j=0; j<g.vexnum; j++) {
			if(i==j)g.arcs[i][j]=0;
			else g.arcs[i][j]=Max;
//			g.arcs[i][j]=Max;
		}
	}
	for(k=0; k<g.arcnum; k++) {
		cout<<"请输入第"<<k+1<<"条边的起点、终点和权重：";
		cin>>v1>>v2>>w;
		i=LocateVex(g, v1);
		j=LocateVex(g, v2);
		while(i==-1||j==-1||w==0) {
			cin.clear();
			cin.sync(); //清空缓冲区
			cout<<"输入错误请重新输入：";
			cin>>v1>>v2>>w;
			i=LocateVex(g, v1);
			j=LocateVex(g, v2);
		}
		g.arcs[i][j]=g.arcs[j][i]=w;
//		g.arcs[i][j]=w;
	}
	/***********************************/
}//CreateGraph

void shortDIJ(Graph g,int v0) {
	int i=0,v,w,Min,n=g.vexnum;
	int s[n],d[n],p[n];
	char temp[n];
	for(v=0; v<g.vexnum; v++) {
		s[v]=0;
		d[v]=g.arcs[v0][v];
		if(d[v]<Max)p[v]=v0;
		else p[v]=-1;
	}
	s[v0]=1;
	d[v0]=0;
	for(i=1; i<n; i++) {
		Min=Max;
		for(w=0; w<n; w++) {
			if(!s[w]&&d[w]<Min) {
				v=w;
				Min=d[w];
			}
		}
		s[v]=1;
		for(w=0; w<n; w++) {
			if(!s[w]&&d[v]+g.arcs[v][w]<d[w]) {
				d[w]=d[v]+g.arcs[v][w];
				p[w]=LocateVex(g, g.vexs[v]);
			}
		}
	}
	for(i=0; i<n; i++) {
		if(i!=v0&&d[i]<Max) {
			cout<<"从 "<<g.vexs[v0]<<" 到 "<<g.vexs[i]<<" 的最短路由为：";
			Min=0;
			for(w=p[i]; w!=v0; w=p[w]) {
				temp[Min++]=g.vexs[w];
			}
			cout<<g.vexs[v0];
			for(w=Min-1; w>=0; w--) {
				cout<<"->"<<temp[w];
			}
			cout<<"->"<<g.vexs[i];
//			cout<<"\t，代价为："<<d[i];
			printf("%5c\t，代价为：%d",' ',d[i]);
			cout<<"\n";
		} else if(d[i]==Max) {
			cout<<-1<<" ";
		}
	}
	cout<<"节点 "<<g.vexs[v0]<<" 的路由表如下：\n";
	cout<<"---------\n";
	cout<<"|   "<<g.vexs[v0]<<"\t|\n";
	cout<<"---------\n";
	for(i=0; i<n; i++) {
		if(g.vexs[i]!=g.vexs[v0]) {
			cout<<"| "<<g.vexs[i]<<"->"<<d[i]<<"\t|\n";
		}
	}
	cout<<"---------\n";
}

void showGraph(Graph g) {
	int i;
	printf("%6c",' ');
	for(i=0; i<g.vexnum; i++) {
		printf("%6c",g.vexs[i]);
	}
	cout<<"\n";
	for(i=0; i<g.vexnum; i++) {
		printf("%6c",g.vexs[i]);
		for(int j=0; j<g.vexnum; j++) {
			if(g.arcs[i][j]==Max) {
				printf("%6s","∞");
			} else printf("%6d",g.arcs[i][j]);
		}
		cout<<"\n";
	}
}
int main() {
	Graph g;
	int a=mm;
	char v0;
	CreateGraph(g);
	showGraph(g);
	while(1) {
		cout<<"请输入起点（输入'q'退出）：";
		cin>>v0;
		if(v0=='q')break;
		a=LocateVex(g,v0);
		while(a==-1) {
			cout<<"输入错误请重新输入：";
			cin>>v0;
			if(v0=='q'){
				a=-1;
				break;
			}
			a=LocateVex(g,v0);
		}
		if(a==-1)break;
		shortDIJ( g, a);
	}
	return 0;
}//main
/*
6
8
a b c d e f
a f 100
a e 30
a c 10
b c 5
c d 50
d f 10
e d 20
e f 60
*/