网站手机适配跳转,做简历网站,淮安市哪里有做网站,汽车之家车报价大全实验七 基于 Dijsktra 算法的最短路径求解 【实验目的】
掌握图的邻接矩阵表示法#xff0c;掌握采用邻接矩阵表示法创建图的算法。掌握求解最短路径的 Dijsktra 算法。 【实验内容】 问题描述 一张地图包括 n 个城市,假设城市间有 m 条路径(有向图),每条路径的长度 已知。给…实验七 基于 Dijsktra 算法的最短路径求解 【实验目的】
掌握图的邻接矩阵表示法掌握采用邻接矩阵表示法创建图的算法。掌握求解最短路径的 Dijsktra 算法。 【实验内容】 问题描述 一张地图包括 n 个城市,假设城市间有 m 条路径(有向图),每条路径的长度 已知。给定地图的一个起点城市和终点城市,利用 Dijsktra 算法求出起点到终 点之间的最短路径。 输入要求 多组数据,每组数据有 m3 行。第一行为两个整数 n 和 m,分别代表城市个数 n 和路径条数 m。第二行有 n 个字符,代表每个城市的名字。第三行到第 m2 行每 行有两个字符 a、b 和一个整数 d,代表从城市 a 到城市 b 有一条距离为 d 的路。 最后一行为两个字符,代表待求最短路径的城市起点和终点。当 n 和 m 都等于 0 时,输人结束。 输出要求 每组数据输出2行。第1行为一个整数,为从起点到终点之间最短路的长度。 第 2 行为一串字符串,代表该路径。每两个字符之间用空格隔开。 输入样例 3 3 A B C A B 1 B C 1 C A 3 A C 6 8 A B C D E F A F 100 A E 30 A C 10 B C 5 C D 50 E D 20 E F 60 D F 10 A F 0 0 输出样例 2 A B C 60 A E D F 【实验提示】 此实验内容即为教材算法 7.15 的扩展原算法求出源点 v0 到图中其余所有 顶点的最短路径。本实验要求求出一个指定起点到一个指定终点的最短路径。 为了提高算法的效率,在求解时,可以加以判断,当已求得的终点为指定终点 时,则可以终止求解,按要求输出相应结果。
#includestdio.h
#includestring.h
#define INF 32767
#define MAXVEX 30
int dist[MAXVEX]; //建立dist数组int path[MAXVEX]; //建立path数组int S[MAXVEX]; //建立S数组typedef char VertexType;typedef struct graph
{int n,e;VertexType vexs[MAXVEX];int edges[MAXVEX][MAXVEX];
}MGraph;void CreateMGraph(MGraph G,int n,int e)
{int value;char temp_i;char temp_j;G.nn;G.ee;for(int i0;in;i){for(int j0;jn;j){if(ij)G.edges[i][j]0;elseG.edges[i][j]32767;}}for(int j0;jG.n;j){getchar();scanf(%c,G.vexs[j]);}int temp_number_i;int temp_number_j;for(int j0;je;j){getchar();scanf(%c %c %d,temp_i,temp_j,value);for(int i0;in;i){if(G.vexs[i]temp_i)temp_number_ii;if(G.vexs[i]temp_j)temp_number_ji;}G.edges[temp_number_i][temp_number_j]value;}}void DispMGraph(MGraph G)
{printf(输出顶点信息\n);for(int i0;iG.n;i){printf(%c,G.vexs[i]);} printf(\n输出邻接矩阵\n);printf(\t);for(int i0;iG.n;i)printf(%8c,G.vexs[i]); for(int i0;iG.n;i){printf(\n%8c,G.vexs[i]);for(int j0;jG.n;j){if(G.edges[i][j]32767) //两点之间无连接时权值为默认的32767// 在无向图中一般用0表示在有向图中一般用∞,// 这里为了方便统一输出 ∞printf(%8s, ∞);elseprintf(%8d,G.edges[i][j]);}printf(\n);}
}void Dijkstra(MGraph g, int v)
{ //求从v到其他顶点的最短路径int mindis,i,j,u0;for (i0;ig.n;i){ dist[i]g.edges[v][i]; //距离初始化S[i]0; //S[]置空if (g.edges[v][i]INF) //路径初始化path[i]v; //v→i有边时置i前一顶点为velse //v→i没边时置i前一顶点为-1path[i]-1;}S[v]1; //源点编号v放入S中for (i0;ig.n-1;i) //循环向S中添加n-1个顶点{ mindisINF; //mindis置最小长度初值for (j0;jg.n;j) //选取不在S中且有最小距离顶点uif (S[j]0 dist[j]mindis) { uj;mindisdist[j];}S[u]1; //顶点u加入S中for (j0;jg.n;j) //修改不在s中的顶点的距离if (S[j]0)if (g.edges[u][j]INF dist[u]g.edges[u][j]dist[j]){ dist[j]dist[u]g.edges[u][j];path[j]u;}}
}void Print(MGraph G,int v,int w)
{printf(\n);for(int i0;iG.n;i){if(i!v dist[i]!INFiw){printf(%c到%c的最短距离为%d\n,G.vexs[v],G.vexs[i],dist[i]);}else if(dist[i]INFiw){printf(%c与%c之间无路径\n,G.vexs[v],G.vexs[i]); } }
}static void Dispath(MGraph g, int v,int w)
{int i, j, k;int apath[MAXVEX], d; //存放一条最短路径(逆向)及其顶点个数//循环输出从顶点v到i的路径for(i 0; i g.n; i){if(S[i] 1 i ! viw){printf(%d\n,dist[i]);d 0; apath[d] i; //添加路径上的终点k path[i];if(k -1) //没有路径的情况printf(无路径\n);else //存在路径时输出该路径{while(k ! v){d;apath[d] k;k path[k];}d; apath[d] v; //添加路径上的起点printf(%c , g.vexs[apath[d]]); //先输出起点for(j d - 1; j 0; j--) //再输出其余顶点printf( %c , g.vexs[apath[j]]);printf(\n);}}}
}int main()
{MGraph G;int n,e;do{scanf(%d%d,n,e);if(n0n0)break;CreateMGraph(G,n,e);char a,b;getchar();scanf(%c %c,a,b);int indexa,indexb;for(int i0;iG.n;i){if(aG.vexs[i])indexai;if(bG.vexs[i])indexbi; }Dijkstra(G,indexa);Dispath(G,indexa,indexb);}while(1);return 0;}
