asdf终极版本.zip

#include <stdio.h> //#include <stdlib.h> //#include <string.h> #define INFINITY 1000 //定义一个权值的最大值 #define MAX_VERTEX_NUM 20 //图的最大顶点数 enum BOOL {False,True}; typedef struct { int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点和边数 } Graph; void CreateGraph(Graph &G,Graph &G1); //生成图的邻接矩阵 void ShortestPath_DiJ(Graph G,int,int[][MAX_VERTEX_NUM],int[]); //用迪杰斯特拉算法求从某一源点到其余顶点的最短路径 void Print_ShortestPath(Graph G,int,int[][MAX_VERTEX_NUM],int[]); //显示某点与其它点的最短路径 void Print_ShowPath(Graph G,int v0,int v1,int P[][MAX_VERTEX_NUM],int D[]); //显示两点之间的最短路径 void Print_ShowChagePath(Graph G,int v0,int v1); //显示两点之间转站次数最少的路径 int main() { Graph G,G1; //采用邻接矩阵结构的图 char j='y'; int u,v; int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径 int D[MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径的距离 printf("\n\n"); printf("~~~~~~~~~~~~欢迎光临城市交通指南系统~~~~~~~~~~~~~\n\n为了给您带来更美好的体验.请先阅读演示程序\n\n"); printf("*******演示本程序的使用方法*******\n"); printf("首先输入图的顶点数和弧数.\n\t格式：顶点数 弧数(数据之间用空格隔开)；\n\t例如: 5 7\n"); printf("然后输入各弧和权值.\n\t格式：起点 终点 花费(数据之间用空格隔开)；\n\t例如: 1 2 10\n\t 1 3 18\n\t 2 4 5\n\t 3 2 5\n\t 4 3 2\n\t 4 5 2\n\t 5 3 2\n"); printf("再输入从哪个起点出发，例如:1\n"); printf("再输入从哪个终点结束，例如:4\n"); printf("程序将会找出从1到4的最少花费和最短路径.\n"); printf("15 1->2->4\n"); printf("程序将会找出从1到其余顶点的最少花费和最短路径.\n"); printf("10 1->2\n17 1->2->4->3\n15 1->2->4\n17 1->2->4->5\n"); printf("*******演示程序执行完毕*******\n\n"); while(j!='N'&&j!='n') { CreateGraph(G,G1); //生成邻接矩阵结构的图 if(!G.arcs) return 0; printf("起始点为:\n"); scanf("%d",&u); //输入迪杰斯特拉算法中的起始顶点 printf("终止点为:\n"); scanf("%d",&v); //输入迪杰斯特拉算法中的终点顶点 ShortestPath_DiJ(G,u,P,D); //利用迪杰斯特拉算法求最短路径 Print_ShowPath(G,u,v,P,D); //显示起始点到终止点的最短路径 printf("\n"); Print_ShowChagePath(G1,u,v); //显示两点之间的最少转站路径 printf("\n"); Print_ShortestPath(G,u,P,D); //显示起始点到其他各点的最短路径 printf("\n"); printf("程序执行完毕，继续进行吗?(Y/N)(不区分大小写)\n"); scanf(" %c",&j); while(j != 'y' && j != 'Y' && j != 'n' && j != 'N') { printf("输入错误！是否继续执行程序？(Y/N)(不区分大小写)\n"); scanf(" %c",&j); } } return 0; } void CreateGraph(Graph &G,Graph &G1) //构造邻接矩阵结构的图G { int i,j; int start,end,weight; printf("请输入图的顶点数和弧数(顶点数 弧数)(数据之间用空格隔开):\n"); scanf("%d %d",&G.vexnum,&G.arcnum); //输入图的顶点数和边数 G1.vexnum=G.vexnum;G1.arcnum=G.arcnum; if(G.vexnum > 20){ printf("图的最大顶点数为20，超过20程序执行错误。\n"); return; } for(i=1; i<=G.vexnum; i++) for(j=1; j<=G.vexnum; j++){ G.arcs[i][j]=INFINITY; //初始化邻接矩阵 G1.arcs[i][j]=INFINITY; } printf("输入各弧和权值，格式：起点 终点 花费(数据之间用空格隔开):\n"); for(i=1; i<=G.arcnum; i++) { scanf("%d %d %d",&start,&end,&weight); //输入边的起点和终点及权值 G.arcs[start][end]=weight; //邻接矩阵输入权值（花费大小） G1.arcs[start][end]=1; } } //迪杰斯特拉算法求最短路径（最小花费） void ShortestPath_DiJ(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[]) { //用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v] //若P[v][0]≠0,表明从源点出发存在一条到顶点v的最短路径，该路径存放在P[v]中 //final[v]为True则表明已经找到从v0到v的最短路径 int i,j,w,v; int min; BOOL final[MAX_VERTEX_NUM]; for(v=1; v<=G.vexnum; v++) //初始化 { final[v]=False; D[v]=G.arcs[v0][v]; for(i=0; i<=G.vexnum; i++) P[v][i]=0; //设空路径 if(D[v]<INFINITY) P[v][0]=v0; //若从v0到v有直达路径 } D[v0]=0; final[v0]=True; //初始时，v0属于S集 //开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集 for(i=1; i<=G.vexnum; i++) //寻找其余G.vexnum-1个顶点 { v=0; min=INFINITY; for(w=1; w<=G.vexnum; w++) //寻找当前离v0最近的顶点v if((!final[w])&&(D[w]<min)) { v=w; min=D[w]; } if(!v) break; //若v=0表明所有与v0有通路的顶点均已找到了最短路径，退 final[v]=True; //将v加入S集 for(j=0; P[v][j]!=0; j++) ; P[v][j]=v; //将路径P[v]延伸到顶点v for(w=1; w<=G.vexnum; w++) //更新当前最短路径及距离 if(!final[w]&&(min+G.arcs[v][w]<D[w])) { D[w]=min+G.arcs[v][w]; for(j=0; P[v][j]!=0; j++) P[w][j]=P[v][j]; } } } //显示从顶点u到其余顶点的最短路径及距离 void Print_ShortestPath(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[]) { int v,j; printf("给您推荐到其他地点的花费和路径:\n"); printf("从顶点 %d 到其他顶点的最少花费和最短路径显示为:",v0); printf("\n"); for(v=1; v<=G.vexnum; v++) { if(P[v][0]==0) continue; //表明顶点v0到顶点v没有通路 printf("\t"); if(D[v] < 1000 && D[v] >= 0){ printf("从顶点 %d 到顶点 %d 的花费为 %-4d",v0,v,D[v]); printf("路径为："); for(j=0; P[v][j]!=0; j++) printf("%d->",P[v][j]); }else{ printf("输入地点有误或者花费有误！为不可达目的地！\n"); return; } printf("\b\b \n"); } } void Print_ShowPath(Graph G,int v0,int v1,int P[][MAX_VERTEX_NUM],int D[]) //显示从起点u到终点v2顶点的最短路径及距离 { int j; printf("从顶点 %d 到顶点 %d 的最少花费和最短路径为:\n",v0,v1); printf("\t"); if(D[v1] < 1000 && D[v1] >= 0){ printf("从顶点 %d 到顶点 %d 的花费为 %-4d",v0,v1,D[v1]); printf("路径为："); for(j=0; P[v1][j]!=0; j++) printf("%d->",P[v1][j]); }else{ printf("输入地点有误或者花费有误！为不可达目的地！\n"); return; } printf("\b\b \n"); } void Print_ShowChagePath(Graph G,int v0,int v1) //显示从起点u到终点v2顶点的最短路径及距离 { int j; int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径 int D[MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径的距离 ShortestPath_DiJ(G,v0,P,D); //利用迪杰斯特拉算法求最短路径 printf("给您推荐到终点 %d 的转站次数最少的路径:\n",v1); printf("从顶点 %d 到顶点 %d 的转站次数最少路径为:\n",v0,v1); printf("\t"); if(D[v1] < 1000 && D[v1] >= 0){ printf("从顶点 %d 到顶点 %d 的转站次数最少为 %-4d",v0,v1,D[v1]-1); printf("路径为："); for(j=0; P[v1][j]!=0; j++) printf("%d->",P[v1][j]); }else{ printf("输入地点有误或者花费有误！为不可达目的地！\n"); return; } printf("\b\b \n"); } /* 1 2 2 1 3 2 2 4 3 2 5 3 3 4 2 */ /* 1 2 10 1 3 18 2 4 5 3 2 5 4 3 2 4 5 2 5 3 2 */