数据结构-求图中任意两点最短路径

1、数据结构实验报告实验题目: 求最短路径。实验内容：求图中任意两点间的最短路径。 一、需求分析程序目的是求有向图中任意两点间的最短路径。1、由用户指定图中任意两点。2、输出结果为指定两点间的最短路径。二 概要设计1、定义结构体  typedef struct ArcNode/节点类型int adjvex;struct ArcNode *nextarc; InfoType_Cost cost;InfoType_Length length;ArcNode;typedef struct VNode/城市编号 int No; VertexType city15; ArcNode *f

2、irstarc;VNode,AdjListMAX_VERTX_NUM;typedef struct ALGraph/图AdjList vertices;int vexnum;int arcnum;ALGraph;typedef struct str1 int value_D;int flag_S;D20;typedef struct str2int father;P20;2.定义函数void Analyse_Info()操作结果：读入文件，将信息存入数组ALGraph Create_Graph()操作结果：创建一个图void ShortPath_DIJ(ALGraph G,int v_sou)

3、初始条件：已知图G；操作结果：用Dijkstra算法求任意两点之间最短路径。void InfoCustomer(ALGraph G,str2 p,str1 d,int v_sou,int v_des,int method)操作结果：将最短路径结果呈现给用户。三 详细设计  #define INT_MAX 65534#define INFINITY INT_MAX #define MAX_VERTX_NUM 20#define FALSE -1#define TRUE 1typedef char VertexType;typedef int InfoType_Cost; ty

4、pedef int InfoType_Length;typedef struct ArcNode/节点类型int adjvex;struct ArcNode *nextarc; InfoType_Cost cost;InfoType_Length length;ArcNode;typedef struct VNode/城市编号 int No; VertexType city15; ArcNode *firstarc;VNode,AdjListMAX_VERTX_NUM;typedef struct ALGraphAdjList vertices;int vexnum;int arcnum;AL

5、Graph;typedef struct str1 int value_D;int flag_S;D20;typedef struct str2int father;P20;int arcnum=0,vexnum=0;char city2015;int path52,cost52;char city_15220,city_25220;P Path_cost,Path_len;D Dear_cost,Dear_len;void Analyse_Info()/读入文件，将信息存入数组 FILE *fp;int i=0,j=0,k=0; int flag_1=0,flag_2=0; int City

6、Counter=0,LineCounter=0; fp=fopen("data.txt","r");while(!feof(fp) fscanf(fp,"%s%s %d %dn",city_1i,city_2i,&costi,&pathi);LineCounter+;i+; arcnum=LineCounter;for(i=0;i<20;) for(k=0;k<52;k+) for (j=0,flag_1=0,flag_2=0;j<=i;j+)/剔除重复出现的城市 if(strcmp(cityj,ci

7、ty_1k)=0)flag_1=1; if(strcmp(cityj,city_2k)=0) flag_2=1; if(flag_1=0) strcpy(cityi,city_1k); CityCounter+; i+; if(flag_2=0) strcpy(cityi,city_2k); CityCounter+; i+; if(strlen(cityi)=0) i+;vexnum=CityCounter;fclose(fp);ALGraph Create_Graph()/创建图 ALGraph G; int i=0,j,k; ArcNode *p,*q,*e; Analyse_Info(

8、); G.arcnum=arcnum; G.vexnum=vexnum; for (i=0;i<20;i+) G.verticesi.firstarc=(ArcNode*)malloc(sizeof(ArcNode); G.verticesi.firstarc->nextarc=NULL; printf("*序号城市名*n"); for (i=0;i<G.vexnum;i+) G.verticesi.No=i; strcpy(G.verticesi.city,cityi); printf(" %d%sn",G.verticesi.No,

9、G.verticesi.city); for (i=0;i<52;i+) for (j=0;j<20;j+)if(strcmp(cityj,city_1i)=0) for (k=0;k<20;k+)if(strcmp(cityk,city_2i)=0) p=G.verticesj.firstarc;while(p!=NULL) q=p;p=p->nextarc;e=(ArcNode*)malloc(sizeof(ArcNode); e->adjvex=k;e->cost=costi;e->length=pathi;e->nextarc=NULL;

10、q->nextarc=e; return G;void ShortPath_DIJ(ALGraph G,int v_sou)/用Dijkstra算法求最短路径 int i,j,no_cost,no_path;int min_cost,min_len;ArcNode *p,*p1,*p2; for (i=0;i<20;i+) /初始化辅助向量 Path_costi.father=i; Path_leni.father=i;for (i=0;i<20;i+) Dear_costi.value_D=INFINITY; Dear_leni.value_D=INFINITY;Dear_

11、costi.flag_S=FALSE; Dear_leni.flag_S=FALSE;p=G.verticesv_sou.firstarc;p=p->nextarc;Dear_lenv_sou.flag_S=TRUE;Dear_costv_sou.flag_S=TRUE;while(p) Dear_lenp->adjvex.value_D=p->length;Dear_costp->adjvex.value_D=p->cost;Path_lenp->adjvex.father=v_sou;Path_costp->adjvex.father=v_sou;

12、p=p->nextarc; for (i=1;i<G.vexnum;i+)/开始主循环，每次求得v0到某个顶点的最短路径min_len=INFINITY;min_cost=INFINITY;for (j=0;j<G.vexnum;j+) /找最小的Dj=minDi if( Dear_lenj.value_D<min_len && Dear_lenj.flag_S=FALSE) min_len=Dear_lenj.value_D; no_path=j;if(Dear_costj.value_D<min_cost && Dear_cos

13、tj.flag_S=FALSE)min_cost=Dear_costj.value_D;no_cost=j;Dear_lenno_path.flag_S=TRUE; Dear_costno_cost.flag_S=TRUE;p1=G.verticesno_path.firstarc;for (p1=p1->nextarc;p1!=NULL;p1=p1->nextarc) /更新 if(Dear_lenp1->adjvex.value_D>(min_len+p1->length)&&Dear_lenp1->adjvex.flag_S=FALSE

14、) Dear_lenp1->adjvex.value_D=min_len+p1->length; Path_lenp1->adjvex.father=no_path;p2=G.verticesno_cost.firstarc;for (p2=p2->nextarc;p2!=NULL;p2=p2->nextarc) if(Dear_costp2->adjvex.value_D>(min_cost+p2->cost)&&Dear_costp2->adjvex.flag_S=FALSE)Dear_costp2->adjvex

15、.value_D=min_cost+p2->cost;Path_costp2->adjvex.father=no_cost; void InfoCustomer(ALGraph G,str2 p,str1 d,int v_sou,int v_des,int method)/通知用户所按要求所寻得的最优路径 int i,len=1;int city;char cities2015; city=pv_des.father;strcpy(cities0,G.verticesv_des.city); while (city!=v_sou)strcpy(citieslen+,G.verticescity.city);city=pcity.father; strcpy(citieslen,G.verticesv_sou.city); len+;for(i=len-1;i>=0;i-)printf("%s",citiesi);if(i!=0) printf("->");printf("n"); if(method=1)if(dv_des.value_D=