北京地铁线路查询
Dijkstra Algorithm Summary
The Dijkstra algorithm is a popular method for finding the shortest path in a graph from a single source to all other nodes. It is widely used in applications like route planning, where the goal is to determine the most efficient route between two points.
Key Concepts:
Graph Representation: The algorithm typically uses an adjacency matrix or list to represent the graph. Each node (station) is connected by edges (lines), with weights representing the distance or number of stations between them.
Priority Queue: A priority queue (min-heap) is used to select the next node with the smallest tentative distance.
Relaxation Process: For each node, its neighbors' distances are updated if a shorter path is found through the current node.
Application to Metro Pathfinding:
Graph Construction: The metro system is modeled as an undirected graph where each station is a node and each line represents an edge connecting multiple nodes.
Edge Weights: Each edge has a weight of 1, representing one station interval along the line.
Lines and Switches: Lines can be looped or have switch stations (non-halting), which are represented by nodes marked as non-switching points in the graph.
Algorithm Steps:
Initialization:
- Read input files to construct the graph, marking switch stations and assigning line IDs.
- Initialize distances to infinity for all nodes except the start node, which is set to 0.
Priority Queue Setup:- Insert all nodes into a priority queue, ordered by their current shortest distance from the start node.
Main Loop:- Extract the node with the smallest tentative distance from the queue.
- For each neighbor, calculate tentative distances through this node and update if shorter paths are found.
Termination:- The process continues until all reachable nodes have been processed or until reaching the target node.
Example Walkthrough:
Given start station "西土城" and end station "北京西站":
Initialize distances for all stations; set start station's distance to 0.
Process each station in order of increasing distance from the start.
Update distances for neighboring stations using their connecting lines until reaching "北京西站".
This approach ensures that once a station's shortest path is determined, it remains optimal throughout subsequent iterations.
Summary Output
The Dijkstra algorithm efficiently finds optimal routes by leveraging priority queues and iterative relaxation of edge weights in weighted graphs. Applied to metro systems like Beijing's network, it provides reliable solutions for minimizing travel time between any two stations through systematic exploration of possible paths.
`plaintext
Dijkstra Algorithm Summary
The Dijkstra algorithm efficiently finds shortest paths in graphs using a priority queue and iterative relaxation of edge weights. It constructs an undirected metro network graph with nodes as stations and edges as lines with unit weights. By initializing distances and processing nodes in order of increasing distance from
Dijkstra Algorithm 迪杰斯特拉算法
北京地铁线路查询涉及最短路径算法的应用，在该代码中采用Dijkstra算法计算任意两站点间的最短路线
问题描述
问题描述
输入形式
启动程序并执行以下操作：首先打开当前目录下的文本文件bgstations.txt；其次导入地铁线路数据；最后分别从标准输入中读取起始站名称和目的站名称（两者均为字符串类型），每个名称占据单独的一行。
输出形式
样例输入
样例说明
输出形式
代码思路
建立图模型的具体方法如下：以各站点作为节点，并为每个节点包含以下信息：站点名称、是否为换乘站；同时记录各线路之间的距离，并标记其所属线路编号。最后完成整个图的构建工作。
一维数学公式BGvertex用于存储每个顶点。其索引值即代表该顶点的编号。二维数学公式BGweights则用于存储图中的边，并且该图是一个无向图的邻接矩阵表示法。对于每一个地铁站点来说，在处理过程中首先需要识别它是否为换乘站：如果它不是换乘站，则将该站点加入到BGvertex中并返回其对应的索引值（即该站点的编号），随后将变量v2赋值给v1（这一操作旨在将当前站点作为后续搜索的新起点），继续扫描剩余顶点；但如果识别到该站点是换乘站，则应在BGvertex中查找是否存在对应记录：如果未找到相关换乘站点，则按照非换乘站的方式进行处理；如果确实存在，则直接返回该换乘站对应的索引值（即其编号）。通过上述步骤我们最终获得了北京地铁站分布所构成的一个无向图模型。
需要注意的是，在获取图之后，我们需要对其进行初始化操作。具体来说，在未连接的顶点对中设置邻接矩阵中的权重值为无穷大（∞），而对于那些不在任何路径连接中的顶点对，则将其在邻接矩阵中的标号设置为-1。这种处理方式有助于使后续应用迪杰斯特拉算法更为便捷。
该代码基于原始Dijkstra算法，在其基础上新增了一个在找到相应顶点后退出的步骤。若读者对此不熟悉，则建议先行了解相关知识，此处不做详细解释。
采用回溯算法中的spath变量（其中，spath变量记录了每个节点的所有可能父节点），并将其应用至地铁线路数据处理中）。随后将所有地铁站点按逆序依次存储于数组board中。初始化时先将起始站加入队列中；然后依次处理后续的所有站点，在处理每个站点的过程中需判断是否需要换乘。每次处理一个站点时会将该路径信息追加到全局路径变量path末尾；最终输出完整的路径信息。
详细代码如下
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNUM 512 //地铁最大站数
#define MAXLEN 16
#define INFINITY 32767
struct station
{
char sname[MAXLEN];
int ischange; //是否为换乘站，0为不是换乘站，1为是换乘站
};
struct weight
{
int wei; //两个站之间的权重，即相差的站数
int ino //两个顶点所在的线号
};
struct station BGvertex[MAXNUM]; //地铁网的顶点
struct weight BGweights[MAXNUM][MAXNUM]; //网络图权重
int Vnum = 0; //实际地铁总站数
int addVertex(struct station p)
{
if (!p.ischange) //不是换乘站
{
BGvertex[Vnum++] = p;
return Vnum - 1;
}
else
{
int i;
for (i = 0; i < Vnum; i++) //查找换乘站
if (!strcmp(p.sname, BGvertex[i].sname))
return i;
BGvertex[Vnum++] = p;
return Vnum - 1;
}
}
void Init_Map()
{
FILE *fp;
int i, j, snum, Ino, Inum, v1, v2;
struct station st;
if ((fp = fopen("bgstations.txt", "r")) == NULL)
printf("Cannot open this file!\n");
fscanf(fp, "%d", &snum);
for (i = 0; i < snum; i++)
{
fscanf(fp, "%d %d", &Ino, &Inum);
v1 = v2 = -1;
for (j = 0; j < Inum; j++)
{
fscanf(fp, "%s %d", st.sname, &st.ischange);
v2 = addVertex(st); //将st加入到顶点数组内并返回数组下标，其中我们用BGvertex数组的下标来表示顶点的编号
if (v1 != -1)
{
BGweights[v1][v2].wei = BGweights[v2][v1].wei = 1; //相邻顶点权重为1
BGweights[v1][v2].ino = BGweights[v2][v1].ino = Ino; //同一线路，线路号相同
} //无向图，v1->v2和v2->v1都要存在邻接矩阵里
v1 = v2;
}
}
for (i = 0; i < Vnum; i++)
{
for (j = 0; j < Vnum; j++)
{
if (!BGweights[i][j].wei)
BGweights[i][j].wei = INFINITY;
if (!BGweights[i][j].ino)
BGweights[i][j].ino = -1;
}
}
fclose(fp);
}
void PrintPath(int v0, int v1, int spath[])
{
char path[80] = {0}, buf[80];
int board[80], bcount = 0, line = -1, sc = 0;
int i;
do{
board[bcount++] = v1;
}while((v1 = spath[v1]) != v0);
board[bcount++] = v0;
line = BGweights[board[bcount - 1]][board[bcount - 2]].ino;
sprintf(buf, "%s-%d(", BGvertex[board[bcount - 1]].sname, line);
strcpy(path, buf);
sc = 1;
for (i = bcount - 2; i > 0; i--, sc++)
{
if (BGweights[board[i]][board[i - 1]].ino != line) //换乘，新的线路号
{
line = BGweights[board[i]][board[i - 1]].ino;
sprintf(buf, "%d)-%s-%d(", sc, BGvertex[board[i]].sname, line);
strcat(path, buf);
sc = 0;
}
}
sprintf(buf, "%d)-%s\n", sc, BGvertex[board[i]].sname);
strcat(path, buf);
puts(path);
}
int main()
{
char ap1[MAXLEN], ap2[MAXLEN];
scanf("%s %s", ap1, ap2);
int v0 = -1, v1 = -1, i;
Init_Map();
for (i = 0; i < Vnum; i++)
{
if (!strcmp(ap1, BGvertex[i].sname))
v0 = i;
if (!strcmp(ap2, BGvertex[i].sname))
v1 = i;
}
int spath[MAXNUM] = {0};
Dijkstra(v0, v1, spath);
PrintPath(v0, v1, spath);
return 0;
}