[데이터 구조] 디 제 스 트 라 알고리즘

/*
	  ：        
	  ：    C    
	    ：VC++ 6.0
	  ：2014-3-25 
*/

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <limits.h>
#include<cstdlib>   //  system("pause");  
//            

#define MAX_NAME 5			//           +1
#define MAX_INFO 20			//             +1
typedef int VRType;			//          
#define INFINITY INT_MAX	//         ∞
#define MAX_VERTEX_NUM 20	//        
typedef char InfoType;		//      
typedef char VertexType[MAX_NAME];	//          
typedef enum{DG, DN, AG, AN} GraphKind; // {   ,   ,   ,   } 

//          
typedef struct
{
	VRType adj; //       。    ， 1( ) 0( )     ； 
				//     ，       
	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;

typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];


//  G     u,           ;    -1。
int LocateVex(MGraph G,VertexType u)
{
	int i;
	for(i = 0; i < G.vexnum; ++i)
		if( strcmp(u, G.vexs[i]) == 0)
			return i;
	return -1;
}

//     (    )   ,     G。
int CreateDN(MGraph *G)
{
	int i,j,k,w,IncInfo;
	char s[MAX_INFO],*info;
	VertexType va,vb;

	printf("      G    ,  ,        ( :1, :0):"
		" (    )
");
	scanf("%d%d%d%*c", &(*G).vexnum, &(*G).arcnum, &IncInfo);
	
	printf("   %d     (<%d   ):
", (*G).vexnum, MAX_NAME);
	for(i=0;i<(*G).vexnum;++i)		//       
		scanf("%s%*c",(*G).vexs[i]);
	for(i=0;i<(*G).vexnum;++i)		//        
	{
		for(j=0;j<(*G).vexnum;++j)
		{
			(*G).arcs[i][j].adj=INFINITY; //  ,            
			(*G).arcs[i][j].info=NULL;
		}
	}
	
	printf("   %d           (       ): 
",(*G).arcnum);
	for(k=0;k<(*G).arcnum;++k)
	{
		scanf("%s%s%d%*c",va,vb,&w);  // %*c      
		i=LocateVex(*G,va);
		j=LocateVex(*G,vb);
		(*G).arcs[i][j].adj=w; //    ，     w 
		if(IncInfo)
		{
			printf("          (<%d   ): ",MAX_INFO);
			scanf("%s%*c", s);
			w = strlen(s);
			if(w)
			{
				info=(char*)malloc((w+1)*sizeof(char));
				strcpy(info,s);
				(*G).arcs[i][j].info=info; //    
			}
		}
	}
	(*G).kind=DN;	//        
	return 1;
}

//  Dijkstra      G v0       v     P[v]      
// D[v]。 P[v][w] 1, w  v0 v            。 
// final[v] 1    v∈S,      v0 v     
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix *P,ShortPathTable *D)
{ 
	int v,w,i,j,min;
	int final[MAX_VERTEX_NUM];
	
	for(v=0;v<G.vexnum;++v)
	{
		final[v]=0;
		(*D)[v]=G.arcs[v0][v].adj;
		for(w=0;w<G.vexnum;++w)
			(*P)[v][w]=0; //      
		if((*D)[v]<INFINITY)
		{
			(*P)[v][v0]=1;
			(*P)[v][v]=1;
		}
	}
	(*D)[v0]=0;
	final[v0]=1; //    ,v0    S  
	for(i=1;i<G.vexnum;++i) //   G.vexnum-1    
	{ //      ,    v0   v       ,  v S  
		min=INFINITY; //      v0        
		for(w=0;w<G.vexnum;++w)
			if(!final[w]) // w   V-S  
				if((*D)[w]<min)
				{
					v=w;
					min=(*D)[w];
				} // w   v0     
		final[v]=1; //  v0     v  S  
		for(w=0;w<G.vexnum;++w) //             
		{
			if(!final[w]&&min<INFINITY && G.arcs[v][w].adj < INFINITY
				&& (min+G.arcs[v][w].adj<(*D)[w]))
			{
				//   D[w] P[w],w∈V-S 
				(*D)[w]=min+G.arcs[v][w].adj;
				for(j=0;j<G.vexnum;++j)
					(*P)[w][j]=(*P)[v][j];
				(*P)[w][w]=1;
			}
		}
	}
}

int main()
{
	int i,j,v0=0; // v0    
	MGraph g;
	PathMatrix p;
	ShortPathTable d;
	
	CreateDN(&g);
	ShortestPath_DIJ(g,v0,&p,&d);
	printf("      p[i][j]  :
");
	for(i=0;i<g.vexnum;++i)
	{
		for(j=0;j<g.vexnum;++j)
			printf("%2d",p[i][j]);
		printf("
");
	}
	printf("%s            ：
",g.vexs[0]);
	for(i=1;i<g.vexnum;++i)
		printf("%s-%s:%d
",g.vexs[0],g.vexs[i],d[i]);
	
	system("pause");
	return 0; 
}

/*
    ：

      G    ,  ,        ( :1, :0): (    )
4 4 0
   4     (<5   ):
a
b
c
d
   4           (       ):
a b 1
a c 2
b d 3
c d 4
      p[i][j]  :
 0 0 0 0
 1 1 0 0
 1 0 1 0
 1 1 0 1
a            ：
a-b:1
a-c:2
a-d:4
       . . . 

*/