OSPF.rar_ospf_ospf dijkstra_ospf 算法

#include<iostream.h> #include<fstream.h> #include<string.h> #define MAXL 10000 typedef struct //路由表结构体 { char routerName;//路由表名 int age;//度量 }Node; Node node[6][5];//六个用于存放路由信息的数组 int n1,n2,n3,n4,n5,n6; int net[6][6]; int input(char str[],int i)//读文件函数 { char ch; int num1=0,num2=0; ifstream infile; infile.open(str); while(!infile.eof()&&infile>>ch) { if(ch>='A'&&ch<='F') { node[i][num1].routerName=ch; num1++; } else { node[i][num2].age=ch-'0'; num2++; } } return num1; } void createGraph()//将路由作为结点，度量作为权值构造图 { int i,j,temp; for(i=0;i<6;i++) for(j=0;j<6;j++) net[i][j]=MAXL; for(i=0;i<6;i++) { if(i==0) temp=n1; else if(i==1) temp=n2; else if(i==2) temp=n3; else if(i==3) temp=n4; else if(i==4) temp=n5; else temp=n6; for(j=0;j<temp;j++)//构造图的邻接矩阵 { net[i][node[i][j].routerName-65]=node[i][j].age; } } for(i=0;i<6;i++)//输出图的邻接矩阵 { for(j=0;j<6;j++) cout<<net[i][j]<<" "; cout<<endl; } } void OSPF()//Dijkstra最短路径算法 { int i,j,count,min,start,end; int S[6]; int temp[6][6]={0};//定义一个中间邻接矩阵用于存放最短路径图 S[0]=0; count=1; while(count<6)//以初始状态中的每个结点进行遍历， { min=100; for(i=0;i<count;i++)//从开始结点开始,然后不断加入 { for(j=0;j<6;j++) { if(net[S[i]][j]<min)//找到权值最小的加入到初始状态中 { min=net[S[i]][j]; start=S[i];//将此最小权值的出发结点保存 end=j;//将到达结点保存 } } } net[start][end]+=100;//标识此结点已经加入到初始状态中 net[end][start]+=100; temp[start][end]=min; S[count]=end;//将找到的新节点加入到初始状态S中 count++;//S中节点数加1 for(i=0;i<count;i++)//将状态S中的所有结点之间的权值全部标记为不可用 { net[S[i]][end]+=100; net[end][S[i]]+=100; } } cout<<endl; cout<<"得到的中间Dijkstra最短路径图邻接矩阵如下:"<<endl; for(i=0;i<6;i++) { for(j=0;j<6;j++) cout<<temp[i][j]<<" "; cout<<endl; } cout<<endl<<"得到A得路由表如下:"<<endl; cout<<"A->B:"<<temp[0][1]<<endl; cout<<"A->C:"<<temp[0][3]+temp[3][4]+temp[4][2]<<endl; cout<<"A->D:"<<temp[0][3]<<endl; cout<<"A->E:"<<temp[0][3]+temp[3][4]<<endl; cout<<"A->F:"<<temp[0][3]+temp[3][4]+temp[4][5]<<endl; } int main() { int i,j; char filenameA[]="A.txt";//定义文件名 char filenameB[]="B.txt"; char filenameC[]="C.txt"; char filenameD[]="D.txt"; char filenameE[]="E.txt"; char filenameF[]="F.txt"; n1=input(filenameA,0);//读取六个文件的路由表信息A-F n2=input(filenameB,1); n3=input(filenameC,2); n4=input(filenameD,3); n5=input(filenameE,4); n6=input(filenameF,5); for(i=0;i<n1;i++) cout<<node[0][i].routerName<<" "<<node[0][i].age<<endl; cout<<endl; for(i=0;i<n2;i++) cout<<node[1][i].routerName<<" "<<node[1][i].age<<endl; cout<<endl; for(i=0;i<n3;i++) cout<<node[2][i].routerName<<" "<<node[2][i].age<<endl; cout<<endl; createGraph(); OSPF(); }