ospf.cpp

此为计算机网络课程设计C/C++源代码 包括一些协议的底层实现

/*OSPF的简单实现*/

#include <iostream.h>
#include <ctype.h>
#include <stdlib.h>

#define MAXINT 65535

//图的类定义
class Graph{
private:
	int Num,*dist,*path,*S;
public:
	int *Edge;
	Graph(int NumVertices)
	{
		Num=NumVertices;
		Edge=new int[NumVertices*NumVertices];		/*用邻接矩阵表示*/
		dist=new int[NumVertices];					/*最短路径长度数组*/
		path=new int [NumVertices];					/*最短路径数组*/
		S=new int[NumVertices];						/*最短路径顶点集*/
	}

	void ShortestPath(const int,const int);
	int choose(const int);
};

/*最短路径算法的实现*/
void Graph::ShortestPath(const int n,const int v)
{
	for (int i=0;i<n;i++)
	{
		dist[i]=Edge[v*n+i];
		S[i]=0;
		if (i!=v && dist[i]<MAXINT)
		{
			path[i]=v;
		}
		else
			path[i]=-1;
	}

	S[v]=1;
	dist[v]=0;

	/*选择当前不在集合S中具有最短路径的顶点u*/
	for (i=0;i<n-1;i++)
	{
		int min=MAXINT;
		int u=v;
		for (int j=0;j<n;j++)
		{
			if (!S[j] && dist[j]<min)
			{
				u = j;
				min = dist[j];
			}
			S[u]=1;						/*将顶点u 加入集合S*/
			for (int w=0;w<n;w++)
			{							/*修改*/
				if (!S[w] && Edge[u*n+w]<MAXINT && dist[u]+Edge[u*n+w]<dist[w])
				{
					dist[w]=dist[u]+Edge[u*n+w];
					path[w]=u;			/*有修改时记录改变的路径*/
				}
			}
		}
	}
}

void main()
{
	cout<<"请输入有向图顶点的个数: "<<endl;
	int NumVertices,temp,v;

	cin>>NumVertices;

	Graph *gSp=new Graph(NumVertices);

	cout<<"请输入源点:"<<endl;
	cin>>v;
	/*应该判断以下v的输入是否是合法*/

	cout<<"已生成数组Edge[NumVertices][NumVertices],请输入各元素的值,"<<endl
		<<"正无穷用-1或其他非数字字符表示:"<<endl;

	/*根据键盘输入初始化Edge[NumVertices][NumVertices]*/
	for (int i=0;i<NumVertices;i++)
	{
		cout<<"请输入"<<NumVertices<<"维矩阵的第"<<i<<"行: "<<endl;
		for (int j=0;j<NumVertices;j++)
		{
			cin>>temp;
			if (temp == -1)
			{
				gSp->Edge[i*NumVertices+j]=MAXINT;
			}
			else
			{
				gSp->Edge[i*NumVertices+j]=temp;
			}
		}
	}

	gSp->ShortestPath(NumVertices,v);
}