shortestpath_dij.cpp

VC6.0环境下编译通过

//ShortestPath_DIJ.cpp

# include <iostream.h>
# include <stdio.h>
# include <malloc.h>
# include <conio.h>
# define INFINITY 1000
# define MAX_VERTEX_NUM 20
# define OK 1
# define ERROR 0 
# define FALSE 0
# define TRUE 1
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int EType;
typedef double InfoType;
typedef int VertexType;
typedef int PathMatrix;
typedef double ShortPathTable; 

typedef struct ArcCell
{  EType adj;
   InfoType info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{  VertexType vexs[MAX_VERTEX_NUM];
   AdjMatrix  arcs;
   int vexnum,arcnum;
   GraphKind kind;
}MGraph;

int CreatUDN(MGraph &G)                                 //CreatUDN() function
{  
	G.vexnum =10;
	G.arcnum = 20;

	int i,j;
   for( i=0;i<G.vexnum;++i)
     for( j=0;j<G.vexnum;++j)
     {  G.arcs[i][j].info=INFINITY;        
	 }

	 G.arcs[0][2].info= 9.84,G.arcs[0][6].info= 5.56,G.arcs[0][8].info= 9.60;
	 G.arcs[1][3].info= 2.59,G.arcs[1][4].info= 9.43,G.arcs[1][7].info= 7.27;
	 G.arcs[2][3].info= 3.99,G.arcs[2][4].info= 5.15,G.arcs[2][7].info= 1.18,G.arcs[2][8].info= 7.83;
	 G.arcs[3][5].info= 9.33,G.arcs[3][6].info= 6.60,G.arcs[3][9].info= 5.38;
	 G.arcs[4][6].info= 8.52,G.arcs[4][8].info= 3.41;
	 G.arcs[5][6].info= 6.47,G.arcs[5][7].info= 0.82;
	 G.arcs[6][7].info= 4.16,G.arcs[6][8].info= 8.39,G.arcs[6][9].info= 5.22;
	 
	 for(i=0;i<G.vexnum;i++)
		 for(j=i+1;j<G.vexnum;j++)
			 G.arcs[j][i] = G.arcs[i][j];

	 
   return (OK);
}//end CreatVDN() function

int CreatUDN_old(MGraph &G)                                 //CreatUDN() function
{  
	int i=0,j=0,k,vi,vj,w;
   cout<<"Please input the number of G.vexnum (eg,G.vexnum=6) : ";
   cin>>G.vexnum;
   cout<<"Please input the number of G.arcnum (eg,G.arcnum=8) : ";
   cin>>G.arcnum;
   for(i=0;i<G.vexnum;++i)
     for(j=0;j<G.vexnum;++j)
     {  G.arcs[i][j].info=INFINITY;        
	 }
   cout<<"Plese input arc(Vi-->Vj):"<<endl
	   <<"For example:"<<endl<<"------------"<<endl
	   <<"(Vi=1,Vj=6,Weight=100),(Vi=1,Vj=5,Weight=30),(Vi=1,Vj=3,Weight=10)"<<endl
	   <<"(Vi=2,Vj=3,Weight=5),(Vi=3,Vj=4,Weight=50),(Vi=4,Vj=6,Weight=10)"<<endl
	   <<"(Vi=5,Vj=6,Weight=60),(Vi=5,Vj=4,Weight=20)..."<<endl;
   for(k=0;k<G.arcnum;++k)
   {   cout<<endl<<"Please input the "<<k+1<<"th arc's vi (0<vi<"<<G.vexnum+1<<"): ";
       cin>>vi;
       cout<<"Please input the "<<k+1<<"th arc's vj (0<vj<"<<G.vexnum+1<<"): ";
       cin>>vj;
       cout<<"Please input the "<<k+1<<"th arc's weight (0<weight<"<<INFINITY<<"): ";
       cin>>w;
       i=vi;
       j=vj;
       while(i<1||i>G.vexnum||j<1||j>G.vexnum||w<0||w>=INFINITY)
       {   
	   cout<<"Input ERROR!"<<endl
		   <<"Please input the "<<k+1<<"th arc's vi (0<vi<"<<G.vexnum+1<<"): ";
	   cin>>vi;
	   cout<<"Please input the "<<k+1<<"th arc's vj (0<vj<"<<G.vexnum+1<<"): ";
	   cin>>vj;
	   cout<<"Please input the "<<k+1<<"th arc's weight (0<weight<1000): ";
	   cin>>w;
	   i=vi;
	   j=vj;
       }//end of while
   i--;
   j--;         
   G.arcs[i][j].info=w;
   }//end of for(k=0;k<G.arcnum...)
   return (OK);
}//end CreatVDN() function


void ShortestPath_DIJ(MGraph G,int v0,PathMatrix Path[MAX_VERTEX_NUM][MAX_VERTEX_NUM],ShortPathTable Dist[MAX_VERTEX_NUM])
{   
	int i,j,v,w,final[MAX_VERTEX_NUM];
	InfoType min;
    for(v=0;v<G.vexnum;++v)
	{  final[v]=FALSE;
       Dist[v]=G.arcs[v0][v].info;
	   for(w=0;w<G.vexnum;++w)
		   Path[v][w]=FALSE;
	   if(Dist[v]<INFINITY)
	   {  Path[v][v0]=v0+1;//TRUE;
	      Path[v][v]=v0+1;//TRUE;
	   }  //end of if
	 }//end of for(v=0;v<G.vexnum...)
	Dist[v0]=0;
	final[v0]=TRUE;

    printf("\nVertice");
	for(i=0;i<G.vexnum;i++)
		 printf("%3d",i+1);         
	printf("\n");
	printf("S= 1,v=%d:",v0+1);      
	for(i=0;i<G.vexnum;i++)
			printf("%6.2f",Dist[i]);  
	printf("\n");

    for(i=1;i<G.vexnum;++i)         //Do the rest of G.vexnum-1 node 
	{
		min=INFINITY;
		for(w=0;w<G.vexnum;++w)
			if(!final[w] && Dist[w]<min)
			{
				v=w;
				min=Dist[w];
			}//end of if
		final[v]=TRUE;
		printf("S=%2d,v=%2d:",i+1,v+1);
		for(w=0;w<G.vexnum;++w)
		{
			if(!final[w]&&(min+G.arcs[v][w].info<Dist[w]))
			{
				Dist[w]=min+G.arcs[v][w].info;
				//for(j=0;j<G.vexnum;j++)
				//    Path[w][j]=Path[v][j];
				Path[w][w]=v+1;//TRUE;
			}//end of if				
			printf("%6.2f",Dist[w]);
		}//end of for(w=0;w<G.vexnum;++w)  
		printf("\n");
	}//end of for(i=1;,,,)
	///*
    printf("\n        1  2  3  4  5  6  7  8  9 10");
	for(i=0;i<G.vexnum;i++){
		printf("\n %5d",i+1);
		for(j=0;j<G.vexnum;j++){
            if(Path[i][j])printf("%3d",Path[i][j]);
			else printf("   ");
		}
	}
	//*/

}//ShortPath_DIJ();

void main()                                                   //main() function
{   MGraph G;
    int v0=0;                                                 //modify
	int i,j;
	PathMatrix Path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	ShortPathTable Dist[MAX_VERTEX_NUM];
	cout<<"ShortestPath_DIJ.cpp"<<endl<<"===================="<<endl<<endl;
    if(CreatUDN(G))
	cout<<endl<<"Create MGraph success !"<<endl<<"InitMGraph are Show:"<<endl<<"--------------------"<<endl;
    
    printf("Vertice");
	for(i=0;i<G.vexnum;i++)    
		 printf("%5d",i+1);       
	printf("\n");   
	for(i=0;i<G.vexnum;i++)
	{   printf("%5d ",i+1); 
		for(j=0;j<G.vexnum;j++)   
              printf("%4.2f ",G.arcs[i][j].info);  
	    printf("\n");
	}//end of for(i=0;i<G.vexnum;i++)

    cout<<endl<<"By Dijkstra Algorithm:"<<endl<<"----------------------"<<endl;
	for(v0=0;v0<G.vexnum;v0++)
		ShortestPath_DIJ(G,v0,Path,Dist);
		

    cout<<endl<<"...OK!..."<<endl;	
    getch();
}//end of main() function