dijkstra_new.cpp

数据结构中表达式求值算法问题

#include <stdio.h>
#define MaxVertexNum 100        /*最大顶点数设为100*/
#define TRUE 1
#define FALSE 0
#define INFINITY 32000
#define M 32000

typedef int VertexType;         /*顶点类型设为整型*/
typedef int EdgeType;           /*边的权值设为整型*/
typedef struct {
       VertexType vexs[MaxVertexNum]; /*顶点表*/
       EdgeType edges[MaxVertexNum][MaxVertexNum]; /*邻接矩阵，即边表*/
       int vexnum,e;                       /*顶点数和边数*/
}MGraph;/*MGragh是以邻接矩阵存储的图类型*/


typedef VertexType PathFrom[MaxVertexNum];
typedef EdgeType ShortPathTable ;
void ShortestPath_Dijkstra(MGraph G,int v0,PathFrom &P, ShortPathTable *D)
{     /*用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其路径长度D[v]*/
	  /*若P[w]=v，表示从v到w是当前求得的最短路径*/
	  /*final[v] 为TRUE当且仅当v∈S, 即已经求得从v0到v的最短路径*/
	  /*常量INFINITY为边上权值可能的最大值*/
	  int final[MaxVertexNum],v,w,i,min;
	  
	  for (w=0; w<G.vexnum; ++w)  P[w]=-1;  /*设空路径*/
	  for (v=0;v<G.vexnum;++v)
	  {   
		  final[v]=FALSE; D[v]=G.edges[v0][v];
		  if(D[v]<M)  P[v] = v0;
	  }   

	  D[v0]=0; final[v0]=TRUE;        /*初始化，v0顶点属于S集*/
	   /*开始主循环，每次求得v0到某个v 顶点的最短路径，并加v到集*/
	  for(i=1; i<G.vexnum; ++i)          /*其余G.vexnum-1个顶点*/
	  {  
		 min=INFINITY;               /*min为当前所知离v0顶点的最近距离*/
	     for (w=0;w<G.vexnum;++w)
	       if (!final[w])                /*w顶点在V－S中*/
			   if (D[w]<min) {v=w; min=D[w];} /*寻找最短路径顶点v*/
	     final[v]=TRUE ;                            /*离v0顶点最近的v加入S集合*/
	     for(w=0;w<G.vexnum;++w)                      /*更新当前最短路径*/
	        if (!final[w]&&(min+G.edges[v][w]<D[w]))  /*修改D[w]和P[w],w∈V-S*/
	        { 
				D[w]=min+G.edges[v][w]; 
			    P[w]=v;              /*P[w]=P[v]+P[w]*/
	        }
	  }
}/*ShortestPath._1*/

void main(void)
{   int i,j;
    MGraph G;
	VertexType P[MaxVertexNum];
	EdgeType D[MaxVertexNum];
/*	EdgeType edges[MaxVertexNum][MaxVertexNum]=
	{{INFINITY,INFINITY,10     ,INFINITY,30      ,100     },
	{INFINITY,INFINITY,5       ,INFINITY,INFINITY,INFINITY},
	{INFINITY,INFINITY,INFINITY,50      ,INFINITY,INFINITY},
	{INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,10      },
	{INFINITY,INFINITY,INFINITY,20      ,INFINITY,60      },
	{INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY}
	};   // 教材中 图8.25 例子
*/
	int source = 1; // 杭州
	char cities[][8]= 
	{        //  HZ  SH  XZ  TJ  DL  SY  CC HEB  BJ HHHT LNZ WLMQ  XN  XA  ZZ  WH ZUZ  NC  FZ  GZ  SZ  LZ  NN  GY  CD  KM
        "杭州","上海","徐州","天津","大连","沈阳","长春","哈滨","北京","呼特","兰州","乌鲁","西宁","西安","郑州",
        "武汉","株州","南昌","福州","广州","深圳","柳州","南宁","贵阳","成都","昆明"
	};
	EdgeType edges[MaxVertexNum][MaxVertexNum]=  // 清华教材中 图7.33 例子
	{        //  HZ  SH  XZ  TJ  DL  SY  CC HEB  BJ HHHT LNZ WLMQ  XN  XA  ZZ  WH ZUZ  NC  FZ  GZ  SZ  LZ  NN  GY  CD  KM
/*1.HZ杭州 */  {  M ,200,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,625,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*2.SH上海 */  { 200,M  ,651,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*3.XZ徐州 */  {  M ,651,M  ,674,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,349,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*4.TJ天津 */  {  M ,M  ,674,M  ,M  ,704,M  ,M  ,137,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*5.DL大连 */  {  M ,M  ,M  ,M  ,M  ,397,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*6.SY沈阳 */  {  M ,M  ,M  ,704,397,M  ,305,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*7.CC长春 */  {  M ,M  ,M  ,M  ,M  ,305,M  ,242,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*8.HEB哈滨*/  {  M ,M  ,M  ,M  ,M  ,M  ,242,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*9.BJ北京 */  {  M ,M  ,M  ,137,M  ,M  ,M  ,M  ,M  ,668 ,M  ,M   ,M  ,M  ,695,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*10.HHHT呼*/  {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,668,M  ,1145,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*11.LNZ兰州*/ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M ,1145 ,M ,1892 ,216,676,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*12.WLMQ乌*/  {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,1892,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*13.XN西宁*/  {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,216,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*14.XA西安 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,676,M   ,M  ,M  ,511,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,842,M },
/*15.ZZ郑州 */ {  M ,M  ,349,M  ,M  ,M  ,M  ,M  ,695,M   ,M  ,M   ,M  ,511,M  ,534,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*16.WH武汉 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,534,M  ,409,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*17.ZUZ株州*/ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,409,M  ,367,M  ,675,M  ,672,M  ,902,M  ,M },
/*18.NC南昌 */ { 625,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,367,M  ,622,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*19.FZ福州 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,622,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M },
/*20.GZ广州 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,675,M  ,M  ,M  ,140,M  ,M  ,M  ,M  ,M },
/*21.SZ深圳 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,140,M  ,M  ,M  ,M  ,M  ,M },
/*22.LZ柳州 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,672,M  ,M  ,M  ,M  ,M  ,255,607,M  ,M },
/*23.NN南宁 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,255,M  ,M  ,M  ,M },
/*24.GY贵阳 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,902,M  ,M  ,M  ,M  ,607,M  ,M  ,967,639},
/*25.CD成都 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,842,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,967,M  ,1100},
/*26.KM昆明 */ {  M ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M   ,M  ,M   ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,M  ,639,1100,M }
	};
	G.vexnum=26;G.e=31;

	for(i=0;i<G.vexnum;i++){
		G.vexs[i]=i;
	    for(j=0;j<G.vexnum;j++)
		    G.edges[i][j]=edges[i][j];
	}

	for(i=0;i<G.vexnum;i++){
	    for(j=i;j<G.vexnum;j++)
		    if(G.edges[i][j]!=G.edges[j][i]) printf("Not a symmetric Matrix!\n");
	}

    ShortestPath_Dijkstra(G,source-1,P,D); // from source to other cities

	printf("\n");
	for(i=0;i<G.vexnum;i++)
	{
		printf(" 从%s到%s,全程%4d公里；经过: ",cities[i],cities[source-1],D[i]);
		j=i;
		while(P[j]>=0){
			printf("%s,",cities[j]);
			j=P[j];
		}
		printf("%s\n",cities[source-1]);
	}

	printf("\n");
}