北京地铁票价查询系统:数据结构第七次作业·第四题·北京地铁线路查询&Dijkstra算法 2024-04-30 14:56:23 0 0 一.Dikjstra算法: (部分内容出自博客Dijkstra算法(迪杰斯特拉算法)_持之以恒2016-CSDN博客) 基本思想: Dikjstra算法采用广度优先策略,从起始点v0开始,层层向外拓展。正是如此,导致其搜索成功率较高但是时间复杂度较大为O(n²)。 将顶点划分为两种:集合S:已经确定最短路径的顶点;集合U:没有确定最短路径的顶点。 操作步骤 1.初始:从s开始,S中只有元素S,其他元素都在U中。且U中顶点与s的距离定义为:若U,s直接连接,则其距离就为其邻接矩阵定义的距离。若U,s不直接连接,则其距离为无穷大(INF)。这样定义是因为可以优先考虑与D相邻的顶点,实现BFS。 2.从U中选出距离最小的顶点k,并把k加入到S中。且k的前序就是v0。 3.更新距离:以k为依托,与k直接连接的顶点到v0的距离(但不一定最小)就等于其到k的距离加上k到v0的距离。若这个距离小于当前记录的距离,则这个顶点的前序就是k。 4.重复2,3到遍历结束。 图解示例 ----- S是已计算出最短路径的顶点的集合 ----- U是未计算出最短路径的顶点的集合 ----- C(3)表示顶点C到起点D的最短距离为3 选择顶点D S={D(0)} U={A(∞), B(∞), C(3), E(4), F(∞), G(∞)} 选取顶点C S={D(0), C(3)} U={A(∞), B(13), E(4), F(9), G(∞)} 选取顶点E S={D(0), C(3), E(4)} U={A(∞), B(13), F(6), G(12)} 选取顶点F S={D(0), C(3), E(4), F(6)} U={A(22), B(13), G(12)} 选取顶点G S={D(0), C(3), E(4), F(6), G(12)} U={A(22), B(13)} 选取顶点B S={D(0), C(3), E(4), F(6), G(12), B(13)} U={A(22)} 选取顶点A S={D(0), C(3), E(4), F(6), G(12), B(13), A(22)} U={} 代码如下:void Dijkstra(int v0){ int minweight,minv; int wfound[MAXVEX]={0};//to sign if the shortest path from i to v0 is found for(int i=0;i<vnum;i++){ sweight[i]=mat[v0][i].weight; spath[i]=v0; wfound[i]=0; } sweight[v0]=0; wfound[v0]=1; for(int i=0;i<vnum-1;i++){ minweight =INF; for(int j=0;j<vnum;j++){ if(!wfound[j]&&sweight[j]<minweight){ minv = j; minweight = sweight[minv]; } } wfound[minv]=1; for(int j=0;j<vnum;j++){ if(!wfound[j]&&(minweight + mat[minv][j].weight)<sweight[j]){ sweight[j]=minweight+mat[minv][j].weight; spath[j]=minv; } } }} 二.北京地铁 题面如下: 编写一个程序实现北京地铁最短乘坐(站)线路查询,输入为起始站名和目的站名,输出为从起始站到目的站的最短乘坐站换乘线路。注:1. 要求采用Dijkstra算法实现;2)如果两站间存在多条最短路径,找出其中的一条就行。 【输入形式】 文件bgstations.txt为数据文件(可从课程网站中课程信息处下载),包含了北京地铁的线路及车站信息。其格式如下: <地铁线路总条数> <线路1> <线路1站数> <站名1> <换乘状态> <站名2> <换乘状态> ... <线路2> <线路2站数> <站名1> <换乘状态> <站名2> <换乘状态> ... 说明:文件第一行为地铁总线路数;第二行第一个数为某条地铁线线号(如,1为1号线),第二个数为该条地铁线的总站数(如1号线共有23站),两数之间由一个空格分隔;第三行两个数据分别为地铁站名及换乘状态(0为非换乘站,1为换乘站),两数据间由一个空格分隔;以下同,依次为该线地铁其它站信息。在一条线路信息之后是下条地铁线路信息,格式相同。若某条地铁线为环线,则首站与末站信息相同(如北京地铁2号线,首站信息“西直门 1” ,末站信息为“西直门 1”)。例如本题提供的bgstations.txt文件(可从课程网站中课程信息处下载)内容如下: 13 1 23 苹果园 0 古城 0 八角游乐园 0 八宝山 0 玉泉路 0 五棵松 0 万寿路 0 公主坟 1 军事博物馆 1 木樨地 0 南礼士路 0 复兴门 1 西单 1 ... 2 19 西直门 1 积水潭 0 鼓楼大街 1 ... 西直门 1 ... 该文件表明当前北京地铁共有13条线路(不含郊区线路),接着为每条线路信息。 打开当前目录下文件bgstations.txt,读入地铁线路信息,并从标准输入中读入起始站和目的站名(均为字符串,各占一行)。 【输出形式】 输出从起始站到目的站的乘坐信息,要求乘坐站数最少。换乘信息格式如下: SSN-n1(m1)-S1-n2(m2)-...-ESN 其中:SSN和ESN分别为起始站名和目的站名;n为乘坐的地铁线路号,m为乘坐站数。 【样例输入】 西土城 北京西站 【样例输出】 西土城-10(1)-知春路-13(2)-西直门-4(2)-国家图书馆-9(4)-北京西站 (或西土城-10(1)-知春路-13(2)-西直门-2(1)-车公庄-6(2)-白石桥南-9(3)-北京西站) 【样例说明】 打开文件bgstations.txt,读入地铁线路信息,并从标准输入中读入查询起始站名为“西土城”,目的站名为“北京西站”。程序运行结果两站间最少乘坐站数的乘坐方式为“西土城站乘坐10号线1站至知春路站换乘13号线乘坐2站至西直门站换乘4号线乘坐2站至国家图书馆站换乘9号线乘坐4站至北京西站”。本样例存在两条最少站数的乘坐方式,只要找出一条就可以。 【评分标准】 对于同一个起始站和目的站,如果存在多条最少站数的乘坐方式,只要找出其中一条就可以。测试点全通过得满分。 本题求解分为三个方面:建立图,用Dijkstra算法求出最短路径的前驱集合,用前驱集合输出符合要求的路径。 建立图: 注意,本题的站点是分地铁线给出的,也就是说,换乘站会出现在多条路线中。这也是建图的时候需要注意,并通过此建立线路间联系的。 由于本题没有给出边信息,所以构建边的原则就是:前一个站点和现在的站点必须要用边连接起来:这样的算法是可以解决环路的。要实现这种方法,就需要使用两个变量来存储当前和上一个结点序号。 具体操作如下: 用v1记录上一个站点,开始时v1为-1。v2记录当前输入的站点。 读入v2,若不是换乘站,就将其与直接加入到顶点集中,然后与v1(如果不是-1的话)连接起来。 若v2是换乘站,则其有可能已经被加入到了顶点集中。这时候就要去搜索其是不是在顶点集中,如果使得的话,v2就是这个顶点的下标。如果不是的话,就和上面一个加入到顶点集中。然后和上一个站连接。 代码如下:int add_vex(Vex p){//return index(xia'biao) of p in v[]; if(!p.istransfer){//if p is not a transfer station v[vnum++]=p; return vnum-1;//add p into v and return index } else{ for(int i=0;i<vnum;i++){//if p is already in v[], don't add and return its index if(!strcmp(p.station_name,v[i].station_name)) return i; } v[vnum++]=p;//if p is not in v[],add p into v return vnum-1; }}void create_graph(){//to make the map of Beijing Subway FILE *src = fopen("bgstations.txt","r"); int v1,v2;//v1 is the index of last station,v2 is the index of present station int line_cnt; Vex tmp_vex; fscanf(src,"%d",&line_cnt); for(int i=0;i<line_cnt;i++){ int lineID,staion_cnt; fscanf(src,"%d%d",&lineID,&staion_cnt); v1 = v2 = -1; for(int j=0;j<staion_cnt;j++){ fscanf(src,"%s%d",tmp_vex.station_name,&tmp_vex.istransfer); v2 = add_vex(tmp_vex); if(v1 !=-1){ mat[v1][v2].weight=mat[v2][v1].weight =1; mat[v1][v2].line=mat[v2][v1].line =lineID; } v1 = v2; } } fclose(src);} 用Dijkstra算法求出最短路径前驱path: 方法和代码已经给出,不再重复。 用path求路径: 注意path[i]是i的前驱,所以要求v1到v2的路径我们只能倒过来从v2开始找。找到的下标存在final_path这个数组里面。但是注意这个路径是倒过来找的,所以我们需要把这个数组在逆置一下,变成顺着的路径。 对于输出部分: 由于我们只输出换乘站(和高德差不多),所以我们需要记录当前在哪条线上面,以及在这条线上走过了多少站。到路线发生变化的时候再输出换乘站。代码如下int tmp = index_e; while(tmp!=index_b){ final_path[path_cnt++]=tmp; tmp = spath[tmp]; } final_path[path_cnt++]=tmp; reverse(); put_path();void reverse(){ int temple[MAXVEX]={0}; for(int i=0;i<path_cnt;i++){ temple[path_cnt-1-i]=final_path[i]; } for(int i=0;i<path_cnt;i++){ final_path[i]=temple[i]; }}void put_path(){ int now,last,way_now,len; last =0,now =1; way_now = mat[final_path[last]][final_path[now]].line; len = 0; printf("%s",v[final_path[0]].station_name); for(;now<path_cnt;now++){ if(way_now!=mat[final_path[last]][final_path[now]].line){ printf("-%d(%d)-%s",way_now,len,v[final_path[last]].station_name); way_now = mat[final_path[last]][final_path[now]].line; len = 0; } len++; last = now; } printf("-%d(%d)-%s",way_now,len,v[final_path[last]].station_name);} 最后附上完整代码:#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXVEX 1000#define INF 32767typedef struct station{ char station_name[32]; int istransfer; //if the station is a transfer station} Vex;typedef struct edge{ int weight; int line; //line of the edge} Edge;Vex v[MAXVEX]; //vertex of stationint vnum = 0; //number of stationEdge mat[MAXVEX][MAXVEX]; //adjacency matrixint add_vex(Vex p){ //return index(xia'biao) of p in v[]; if (!p.istransfer) { //if p is not a transfer station v[vnum++] = p; return vnum - 1; //add p into v and return index } else { for (int i = 0; i < vnum; i++) { //if p is already in v[], don't add and return its index if (!strcmp(p.station_name, v[i].station_name)) return i; } v[vnum++] = p; //if p is not in v[],add p into v return vnum - 1; }}void create_graph(){ //to make the map of Beijing Subway FILE *src = fopen("bgstations.txt", "r"); int v1, v2; //v1 is the index of last station,v2 is the index of present station int line_cnt; Vex tmp_vex; fscanf(src, "%d", &line_cnt); for (int i = 0; i < line_cnt; i++) { int lineID, staion_cnt; fscanf(src, "%d%d", &lineID, &staion_cnt); v1 = v2 = -1; for (int j = 0; j < staion_cnt; j++) { fscanf(src, "%s%d", tmp_vex.station_name, &tmp_vex.istransfer); v2 = add_vex(tmp_vex); if (v1 != -1) { mat[v1][v2].weight = mat[v2][v1].weight = 1; mat[v1][v2].line = mat[v2][v1].line = lineID; } v1 = v2; } } fclose(src);}int visited_dfs[MAXVEX] = {0};void DFS(int i){ printf("%s\n", v[i].station_name); visited_dfs[i] = 1; for (int j = 0; j < vnum; j++) { if (mat[i][j].weight > 0 && visited_dfs[j] == 0) { DFS(j); } }}int sweight[MAXVEX]; //to record the shortest len between i and v0int spath[MAXVEX]; //to record the shortest pathvoid Dijkstra(int v0){ int minweight, minv; int wfound[MAXVEX] = {0}; //to sign if the shortest path from i to v0 is found for (int i = 0; i < vnum; i++) { sweight[i] = mat[v0][i].weight; spath[i] = v0; wfound[i] = 0; } sweight[v0] = 0; wfound[v0] = 1; for (int i = 0; i < vnum - 1; i++) { minweight = INF; for (int j = 0; j < vnum; j++) { if (!wfound[j] && sweight[j] < minweight) { minv = j; minweight = sweight[minv]; } } wfound[minv] = 1; for (int j = 0; j < vnum; j++) { if (!wfound[j] && (minweight + mat[minv][j].weight) < sweight[j]) { sweight[j] = minweight + mat[minv][j].weight; spath[j] = minv; } } }}int final_path[MAXVEX] = {0};int path_cnt = 0;void reverse(){ int temple[MAXVEX] = {0}; for (int i = 0; i < path_cnt; i++) { temple[path_cnt - 1 - i] = final_path[i]; } for (int i = 0; i < path_cnt; i++) { final_path[i] = temple[i]; }}void put_path(){ int now, last, way_now, len; last = 0, now = 1; way_now = mat[final_path[last]][final_path[now]].line; len = 0; printf("%s", v[final_path[0]].station_name); for (; now < path_cnt; now++) { if (way_now != mat[final_path[last]][final_path[now]].line) { printf("-%d(%d)-%s", way_now, len, v[final_path[last]].station_name); way_now = mat[final_path[last]][final_path[now]].line; len = 0; } len++; last = now; } printf("-%d(%d)-%s", way_now, len, v[final_path[last]].station_name);}int main(){ for (int i = 0; i < MAXVEX; i++) { for (int j = 0; j < MAXVEX; j++) { mat[i][j].weight = INF; mat[i][j].line = 0; } } create_graph(); char begin[32], end[32]; scanf("%s%s", begin, end); int index_b, index_e; //int flag1=0,flag2=0; for (int i = 0; i < vnum; i++) { if (!strcmp(begin, v[i].station_name)) { index_b = i; //flag1 = 1; } if (!strcmp(end, v[i].station_name)) { index_e = i; //flag2 = 1; } } //DFS(0); //for(int i=0;i<vnum;i++) printf("%d %s\n",i,v[i].station_name); //printf("%d\n",vnum); /*for(int i=0;i<vnum;i++){ for(int j=0;j<vnum;j++){ if(mat[i][j].weight!=INF) printf("%d %d ",mat[i][j].line,mat[i][j].weight); } puts(""); }*/ //printf("%d %d",flag1,flag2); //printf("\n%d %s\n",index_b,v[index_b].station_name); //printf("%d %s",index_e,v[index_e].station_name); Dijkstra(index_b); /*for(int i=0;i<vnum;i++) printf("%d ",spath[i]);*/ int tmp = index_e; while (tmp != index_b) { final_path[path_cnt++] = tmp; tmp = spath[tmp]; } final_path[path_cnt++] = tmp; reverse(); /*for(int i=0;i<path_cnt;i++){ printf("%s ",v[final_path[i]].station_name); }*/ put_path();} 收藏(0)