[学习]广州地铁线路规划大作业

Dijkstra算法应用

一、前言

起因是数据结构作业的期末作业，要求设计一个广州地铁线路规划程序。输入出发站点和目的站点，输出最短乘坐路径和换乘线路方法。

这项作业是对本学期所学的数据结构一个综合考验，比起Dijkstra算法，如何存储地铁线路图，如何将站点名称输出，如何存储图、建立图，如何将中文字符对应到一个可以计算使用的数字，以及线路的更新是本程序的重点。

二、核心函数

1、站点名->数字的转换

广州地铁上的站点都是中文字符，很明显，中文字符无论是制作成邻接表还是邻接矩阵都是不合适的，因此需要一种方法，将广州地铁上上百个站点一一转换成计算机可以用来计算的数字。人工手动更换是绝对的不合适，先不说上百个站点的标记十分累人，更加重要的是这样的程序完全没有任何的可拓展性，它就不能适应新加的地铁站点。 所以，给站点打标记的活还是要交给计算机干，这里采用的方法是，将地铁站所有的站点和站点之间的线路权值存储在同一个文件中。存储方式如下所示，第一个字符表示是哪一条线路，第二个表示始发站，第三个字符串表示终点站，第四个数字表示边的权值。

1
2
4 大学城北 大学城南 1
4 大学城南 …… 1

然后是从上面的数据文件中建图，注意到这个图的邻接矩阵会是一个稀疏矩阵，采用邻接表的方法存储图。部分站点可能是换乘站，为减少换乘站带来的可能问题，此处选择给同名站点名称后添加字符加以区别，例如“万胜围”在4号线出现一次，那么在8号线出现的存储为“万胜围0”以此类推。但是在这样的处理方法会导致各条线路之间不连通，和真实的地铁线路不符合，所以在换乘站之间添加一条边权为0的边连通。 

1
-1 万胜围 万胜围0 0
除此之外，还需要做三件事情，一个是给每一个站点赋予一个独特的id，用于程序计算；二是建立一个id到文本的映射，方便文本输出线路；三是建立一个文本到id的映射，方便将收到的出发站和终点站转换为内置id。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 void subway_system::readData(vector<edge> &edges)
{
	// string a;
	// cin >> a;
	ifstream fin("srcdata");
	int distance, ID[2];
	string line, station[2];

	while (fin >> line >> station[0] >> station[1] >> distance)
	{
		for (int i = 0; i < 2; i++)
		{
			auto findStation = Stations.find(station[i]);
			//查找不到这个站点
			if (findStation == Stations.end())
			{
				ID[i] = Stations.size();
				Stations[station[i]] = pair<string, int>(line, ID[i]);
				station_name.push_back(station[i]);
			}
			//该站点在本线路上已经出现
			else if ((*findStation).second.first == line)
				ID[i] = Stations[station[i]].second;
			//这是一个换乘站点
			else
			{
				string it_name = station[i];
				char c = '1';
				station[i] += c;
				auto it = Stations.find(station[i]);
				while (it != Stations.end() && (*it).second.first != line)
				{
					station[i].back() = ++c;
					it = Stations.find(station[i]);
				}
				if (it == Stations.end())
				{
					ID[i] = Stations.size();
					Stations[station[i]] = pair<string, int>(line, ID[i]);
					station_name.push_back(station[i]);
				}
				else
					ID[i] = Stations[station[i]].second;
				edges.push_back(edge(ID[i], Stations[it_name].second, 0));	//增加边权为0的边
			}
		}

		edges.push_back(edge(ID[0], ID[1], distance));
	}
	n = edges.size() + 1;
	fin.close();
	//cout << Stations.size() << endl;
	return;
}

2、节点存储

地铁站点上是会有非常多的信息，比如说它在本程序中的id，方便Dijkstra算法必须的dis数据，bool类型的known，因此结构化为一个数据体 

1
2
3
4
5
6
7
8
9
struct vertex
{
	size_t dis;	//最短路径算法使用
	int id;		//在程序中的id
	int path;	//父节点，输出从换乘线路使用
	bool known;	//标记是否已经被搜索到
	bool popped;//输出线路使用
	vertex() : dis(inf), known(false), popped(false) {}
};
### 3、Dijkstra算法 标准的Dijkstra算法。函数需要输出最短路径，所以返回一个记录最短路径走法的vector数组，记录从目的地前往始发点的最短路径。在输出线路之前需要考虑一个顺序的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
vector<int> subway_system::getShortestPath(int origin, int destination)
{
	vector<int> res;
	set<int> known;
	//initialize
	vector<vertex> nodes;
	nodes.resize(n);
	for (size_t i = 0; i < nodes.size(); i++)
	{
		nodes[i].id = i;
		nodes[i].path = i;
		nodes[i].popped = false;
	}
	nodes[origin].dis = 0;
	nodes[origin].known = true;
	nodes[origin].path = origin;
	known.insert(origin);
	//calculating

	for (int i = 0; i < n; i++)
	{
		int index = 0, min_dis = inf;
		for (auto &entry : known)
			if (!(nodes[entry].popped) && nodes[entry].dis < min_dis)
			{
				min_dis = nodes[entry].dis;
				index = entry;
			}
		if (index == destination)
			break;

		//cout << station_name[index] << " ";

		nodes[index].popped = true;
		vertex u = nodes[index];

		for (auto &entry : E[u.id])
		{
			if (!nodes[entry.first].known)
			{
				if (nodes[entry.first].dis > nodes[u.id].dis + entry.second)
				{
					nodes[entry.first].known = true;
					known.insert(entry.first);
					nodes[entry.first].dis = nodes[u.id].dis + entry.second;
					nodes[entry.first].path = u.id;
				}
			}
		}
	}
	if (nodes[destination].known == false)
	{
		return res;
	}
	//get path
	stack<int> temp;
	int cur = destination;
	temp.push(cur);
	while (nodes[cur].path != origin)
	{
		cur = nodes[cur].path;
		temp.push(cur);
	}
	temp.push(origin);
	while (!temp.empty())
	{
		res.push_back(temp.top());
		temp.pop();
	}
	return res;
}

4、输出结果

在上一个函数获得了最短路径的id。但是id并不对应站点名，因此还需要一个输出函数，将一串数组转换为人可以看得懂的站点名称，并且还需要输出换乘信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
string subway_system::checkLine(string oringin, string destination)
{
	vector<int> result;
	vector<string> output;
	vector<pair<string,string>> transform;
	int ori = this->Stations[oringin].second;
	int dest = this->Stations[destination].second;
	result = getShortestPath(ori, dest);
	if (result.size() == 0)
	{
		cout << "不存在这样一条道路" << endl;
		string a;
		return a;
	}

	for (int i = 0; i < result.size(); i++)
	{	
		output.push_back(del_num(station_name[result[i]]));
		
	}
	for (int i = 2; i < result.size();i++){
		if (del_num(station_name[result[i]]) == del_num(station_name[result[i - 1]]) && i > 1)
		{
			pair<string, string> temp(Stations[station_name[result[i]]].first, Stations[station_name[result[i - 1]]].first);
			transform.push_back(temp);
		}
	}
	cout << output[0] << "->";
	int j = 0;
	string all_in_one;
	for (int i = 1; i < output.size(); i++)
	{
		if (i == output.size() - 1)
		{
			all_in_one.append( output[i]);
			all_in_one.append("\n");
		}
		else if (output[i] != output[i - 1])
		{
			all_in_one.append(output[i]);
			all_in_one.append("->");
			
		}
		else
		{
			all_in_one.append("从");
			all_in_one.append(transform[j].second);
			all_in_one.append("号线转到");
			all_in_one.append(transform[j++].first);
			all_in_one.append("号线\n");
			
		}
	}
	cout << all_in_one;
	
	std::system("pause");
	return all_in_one;
}

5、建图的数据结构

上面所谓的建图，其实只是完成了边的读入，并没有建立一个邻接表，这段函数的目的就是从边建立一个可以被最短路径算法使用的邻接表 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct edge	//边的数据结构
{
	int u, v, w;
	edge(int U, int V, int W = inf) :u(U), v(V), w(W) {  }
};

void subway_system::makeGraph(vector<edge> &edges)
{
	list<pair<int, int>> tmp;
	for (int i = Stations.size(); i--;)	//几条线路
		E.push_back(tmp);
	for (auto &item : edges)
	{
		E[item.u].push_back(pair<int, int>(item.v, item.w));
		E[item.v].push_back(pair<int, int>(item.u, item.w));
	}
}
## 四、注意事项 也就是尽量不要在window的终端上运行，或者在编译之前将源代码转换为GBK编码，不然终端看见的只有一片乱码。

五、鸣谢

本代码主要来自github上昊C和他的舍友大佬。最初的版本因为有一点点小问题，没有解决0权值边的问题，导致在测试的时候经常崩（后来查实是因为一直压栈最后爆内存了）。仔细排查才最后发现，原来是建图的时候，没有给换乘站一个他们之间连线，导致在输出的时候一直压栈，因为没有到达目的地。

如果也有类似大作业的需求，希望这份代码能帮到你。

#学习 #数据结构
[学习]广州地铁线路规划大作业
http://example.com/2020/12/07/学习/学习-dijkstra/
Author
peach-water
Posted on
December 7, 2020
Licensed under