cpp1.cpp

本程序采用Dijkstra核心算法

/**********************************************************************/
/*                                                                    */
/*                           File "rand.h"                            */
/*                     Random Variate Generation                      */
/*                                                                    */
/*                                                                    */
/**********************************************************************/
#ifndef _RAND_H
#define _RAND_H

#include <stdio.h>
#include <math.h>
#define A 16807L           /* multiplier (7**5) for 'ranf' */
#define M 2147483647L      /* modulus (2**31-1) for 'ranf' */

static long In[16]= {0L,   /* seeds for streams 1 thru 15  */
  1973272912L,  747177549L,   20464843L,  640830765L, 1098742207L,
    78126602L,   84743774L,  831312807L,  124667236L, 1172177002L,
  1124933064L, 1223960546L, 1878892440L, 1449793615L,  553303732L};

static int strm=1;         /* index of current stream */
float ranf();		//uniform [0, 1] random number generator
int stream(int n);	//select generator stream
long seed(long Ik, int n);	//set/get seed
float uniform(float a, float b);	//uniform [a, b] random number generator
int random(int i, int n);	//random integer generator
float exponential(float x);	//exponential random variate generator
float erlang(float x,float s);	//erlang random variate generator
float hyperx(float x,float s);	//hyperexponential random variate generator
float normal(float x,float s);	//normal random variate generator




#include <iostream>
using namespace std;
const int reqstnum=70;        //请求的次数
const int MAXVEX=6;				 //节点数
const float MAXBAND=20;        //为了使输出的tempcost的值为float，把 MAXBAND设为float型
const int NOUT=-1;             //NOUT定义为没有意义的数为-1
float INF=9999;


#endif

/*-------------  UNIFORM [0, 1] RANDOM NUMBER GENERATOR  -------------*/



float ranf()
{
    short *p,*q,k; long Hi,Lo;
    /* generate product using float precision simulation  (comments  */
    /* refer to In's lower 16 bits as "L", its upper 16 bits as "H")  */
    p=(short *)&In[strm]; Hi=*(p+1)*A;                 /* 16807*H->Hi */
    *(p+1)=0; Lo=In[strm]*A;                           /* 16807*L->Lo */
    p=(short *)&Lo; Hi+=*(p+1);    /* add high-order bits of Lo to Hi */
    q=(short *)&Hi;                       /* low-order bits of Hi->LO */
    *(p+1)=*q&0X7FFF;                               /*0111 clear sign bit */
    k=*(q+1)<<1; if (*q&0X8000)  k++;         /* Hi bits 31-45->K */
    /* form Z + K [- M] (where Z=Lo): presubtract M to avoid overflow */
    Lo-=M; Lo+=k; if (Lo<0)  Lo+=M;
    In[strm]=Lo;
    return((float)Lo*4.656612875E-10);             /* Lo x 1/(2**31-1) */
}




int random(int i, int n)    //产生1-25间的一个随机整数
{
	/* 'random' returns an integer equiprobably selected from the   */
    /* set of integers i, i+1, i+2, . . , n.                        */
    if (i>n)  printf("random Argument Error: i > n");
    n-=i; n=(int)((n+1.0)*ranf());
    return(i+n);
}

 





void dijkstra(float cost[MAXVEX][MAXVEX],int n,int v,int des,int store[reqstnum][MAXVEX+2],int retime)//des是终点，v是源点,retime---require time请求的次数
{ 
	float dist[MAXVEX], mindis;  
	int s[MAXVEX], i,j,u,pre,k,path[MAXVEX];
	int zancun[MAXVEX+1];
	for (i=0;i<(MAXVEX+1);i++)	{ zancun[i]=-1;}
	
	for (i=0;i<n;i++)
	{	dist[i]=cost[v][i];			//距离初始化
		s[i]=0;						//s[]置空
		if(cost[v][i]<INF)			//路径初始化
			path[i]=v;
		else
		
			path[i]=-1;
	}	
    s[v]=1;path[v]=0;				//源点编号v放入s中
	for(i=0;i<n;i++)				//循环直到所有的顶点的最短路径都求出
    {	mindis=INF;
		u=-1;
		for(j=0;j<n;j++)				//选取不再s且具有最小距离的顶点u
			if(s[j]==0 && dist[j]<mindis)
			{ 
				u=j;
				mindis=dist[j];
			}
		if(u!=-1)					
		{	s[u]=1;
			for(j=0;j<n;j++)
				if(s[j]==0)
					if(cost[u][j]<INF && dist[u]+cost[u][j]<dist[j])
					{	dist[j]=dist[u]+cost[u][j];
						path[j]=u;
					}
		}
	}


			                    
	       
	     
	      	//输出最短路径的长度，路径顺序输出

	
	
	    
		cout<<" "<<v<<"->"<<des<<":";
		if(s[des]==1)
		{	cout<<"路径长度为"<<dist[des]<<" ";
			k=0; 
		    zancun[MAXVEX]=dist[des];
		    zancun[MAXVEX-1]=v;
			pre=des;
		  while(pre!=v)				//一直回溯到初始顶点
		  {   zancun[k]=pre;
		      	pre=path[pre];
				k=k+1;
		  } 
       
	    //开始往请求数组里存储

	      j=0;
		  for(i=0;i<(MAXVEX+1);i++)
		  {  if(zancun[MAXVEX-i]!=-1)
		  {  store[retime][j]=zancun[MAXVEX-i];
		     j=j+1; 
		  }
		  }
		
       
        i=1;
		cout<<" 经历的节点是:";
		while(store[retime][i]!=-1)
		{	cout<<store[retime][i]<<",";
		    i++;
		}
        cout<<"\n";
		}
		
		else
			cout<<"不存在路径"<<endl;
		}
//dijkstra算法结束





//主函数开始

void main()
{  	int i,j,s1,s2,blocknum=0,baohublocknum=0;//记录工作路径和保户路径被阻塞的次数
    float costshuzu[MAXVEX+1];//  用来存储为了寻找保护路径暂时变成无穷的工作通路的代价.+1是为了与以后计算的下标对应
    int pertectstore[reqstnum][MAXVEX+2];//该二维数组用来存储与store对应的保护通路的路径和长度
	int store[reqstnum][MAXVEX+2]; //第0个元素存储路径的总长度，路径最多MAXVEX个点，最后一个用作数组结束循环语句控制的标志
    void dijkstra(float cost[MAXVEX][MAXVEX],int n,int v,int des,int store[reqstnum][MAXVEX+2],int retime);//示第retime次业务请求
  
	float cost[MAXVEX][MAXVEX]={
		{0,50,10,INF,INF,INF},
		{50,0,15,50,10,INF},
		{10,15,0,15,INF,INF},
		{INF,50,15,0,35,INF},
		{INF,10,INF,30,0,3},
		{INF,INF,INF,3,4,0}};  
   float tempcost[MAXVEX][MAXVEX];
     for(i=0;i<MAXVEX;i++)       //设tempcost的初始值与cost相同
	 { 
		for(j=0;j<MAXVEX;j++)
		   tempcost[i][j]=cost[i][j];
	 }
	
	  for(i=0;i<reqstnum;i++)   //设工作业务矩阵的初始值都是-1，无效。只有存入数字的元素有效
      { 
		for(j=0;j<(MAXVEX+2);j++)
		   store[i][j]=NOUT;
	  }
      
	  for(i=0;i<reqstnum;i++)   //设保护业务矩阵的初始值
      { 
		for(j=0;j<(MAXVEX+2);j++)
		  pertectstore[i][j]=NOUT;
	  }
	  

	  int freeband[MAXVEX][MAXVEX]={    
			{0,20,20,0,0,0},
			{20,0,20,20,20,0},
			{20,20,0,20,0,0},
			{0,20,20,0,20,0},
			{0,20,0,20,0,20},
			{0,0,0,20,20,0}};  //设置存储设需带宽的数组	
	int busyband[MAXVEX][MAXVEX];   //设置存储工作带宽的数组
	for(i=0;i<MAXVEX;i++)            //初始化占用带宽为0
	{
		for(j=0;j<MAXVEX;j++)
					busyband[i][j]=0;
	}
	
	for(i=0;i<reqstnum;)
	{  
		s1=random(0,5);
		s2=random(0,5);
		if(s1!=s2)
		{
			cout<<"第"<<i<<"次业务请求工作路径:";
			dijkstra(tempcost,6,s1,s2,store,i);   //计算工作路径
			
			
		 if(store[i][0]!=-1)  //判断是否找到了工作路径，如果找到那么store[i][0]!=-1	
		 {
		    for(j=1;store[i][j+1]!=-1;j++) //从第一个元素开始是路径的而第一个节点，store设置的MAXVEX+2是因为这一步的极限当路径经过的节点为节点总数时
	
			{ 
			  freeband[store[i][j]][store[i][j+1]]=freeband[store[i][j]][store[i][j+1]]-1;
			     if(freeband[store[i][j]][store[i][j+1]]<=0)
				  {
				    tempcost[store[i][j]][store[i][j+1]]=INF;    //当链路上没有可利用的带宽时，代价设为无穷
				  }
			     else
					 tempcost[store[i][j]][store[i][j+1]]=cost[store[i][j]][store[i][j+1]]+(MAXBAND-freeband[store[i][j]][store[i][j+1]]+1)/MAXBAND; 
			  busyband[store[i][j]][store[i][j+1]]=busyband[store[i][j]][store[i][j+1]]+1;
		  
			}

	        for(j=1;store[i][j+1]!=-1;j++) //把工作路径的代价都设为无穷以便寻找保护路
			{
				costshuzu[j]=tempcost[store[i][j]][store[i][j+1]];
				tempcost[store[i][j]][store[i][j+1]]=INF;
			}

        
	       cout<<"第"<<i<<"次业务请求保护路径:   ";
		   dijkstra(tempcost,6,s1,s2,pertectstore,i);//计算工作通路的专用保护路径
		
		   for(j=1;store[i][j+1]!=-1;j++) 
		   {
			tempcost[store[i][j]][store[i][j+1]]=costshuzu[j];	//把变成无穷的工作通路的代价变回原来的值
		   }
       
	    
		
			if(pertectstore[i][0]!=-1)   //当找到保护路径时，开始调整找到保护通路以后的带宽和代价 
			for(j=1;pertectstore[i][j+1]!=-1;j++) 
			{ 
				freeband[pertectstore[i][j]][pertectstore[i][j+1]]=freeband[pertectstore[i][j]][pertectstore[i][j+1]]-1;
				if(freeband[pertectstore[i][j]][pertectstore[i][j+1]]<=0)
				{
			      tempcost[pertectstore[i][j]][pertectstore[i][j+1]]=INF;    //当链路上没有可利用的带宽时，代价设为无穷
				}
		        else tempcost[pertectstore[i][j]][pertectstore[i][j+1]]=cost[pertectstore[i][j]][pertectstore[i][j+1]]+(MAXBAND-freeband[pertectstore[i][j]][pertectstore[i][j+1]]+1)/MAXBAND; 
		        busyband[pertectstore[i][j]][pertectstore[i][j+1]]=busyband[pertectstore[i][j]][pertectstore[i][j+1]]+1;
		  
			}   
	       else baohublocknum=baohublocknum+1;
		 }
       
    	else blocknum=blocknum+1;
	    i=i+1; 
	  
	   }
  
 }
 
 
 for(i=0;i<reqstnum;i++)
 {   
	{cout<<"\n";
	 for(j=0;j<MAXVEX+2;j++)
		 cout<<store[i][j]<<",";     //输出业务存储矩阵的所有数值
	}
 }


  for(i=0;i<MAXVEX;i++)       
	 { 
	   cout<<"\n";
		for(j=0;j<MAXVEX;j++)
		   cout<<tempcost[i][j]<<",  ";
	 }


    cout<<"\n剩余带宽：";//输出剩余带宽的矩阵
	for(i=0;i<MAXVEX;i++)
	{
		cout<<"\n";
	for(j=0;j<(MAXVEX);j++)
	cout<<freeband[i][j]<<",";
	}
							
					
					
	cout<<"\n占用的带宽";   //输出占用带宽的矩阵
	for(i=0;i<MAXVEX;i++)
	{
		cout<<"\n";
	for(j=0;j<(MAXVEX);j++)
	cout<<busyband[i][j]<<",";	
	
	}


    cout<<"\n工作通路阻塞的次数是"<<blocknum<<"\n";
    cout<<"\n保户通路阻塞的次数是"<<baohublocknum<<"\n";



}