日常生活中，上班下班坐地铁已经是常事，每当我想去某一个远一点的地方，如果有地铁首选就是地铁，因为方便嘛！每次坐地铁，我们都是凭肉眼去得出我们心中最佳的换乘方案，但是，如果对于线路较少的城市来说，这个方法是最快的，但是如果对于线路较多的城市，例如北京或者上海，十几条线路交叉穿梭，我们可能看到都晕了，怎么坐才是时间最短路程最短的，我们要算出来不是不可以但是很麻烦，我们也可以想一想，百度地图的地铁换乘算法是怎么实现的，于是，闲着没事，我就想写一个通用的地铁换乘查询程序，想用计算机运算得出科学一点的换乘方案供自己参考，假设先不考虑站点间的距离差异，我们以乘坐站点数最少为最优方案，依照这个条件去编码实现查找的算法，其实也没用上什么高大上的算法，因为也不会哈哈，话不多说，先上效果图：
有对应城市的线路图：
站点智能提示：
项目结构图：
我的开发思路：
1、采用xml存储站点数据，如下：
2、代码中使用集合初始化线路数据
1 /// <summary>
2 /// 初始化地铁线路数据
3 /// </summary>
4 /// <param name="city">城市</param>
5 public static void InitSubwayLine(CityEnum city)
6 {
7 if (AllSubwayLines != null && AllSubwayLines.Any() && _currentCity == city) return;
8 _currentCity = city;
9 var xmlName = Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "xml/" + city.ToString() + ".xml");
10 _doc = XDocument.Load(xmlName);
11 AllSubwayLines = _doc.Root.Elements().Select(x =>
12 {
13 var line = new SubwayLine
14 {
15 No = x.Attribute("No").Value,
16 Name = x.Attribute("Name").Value,
17 IsRound = x.Attribute("IsRound") == null ? false : bool.Parse(x.Attribute("IsRound").Value),
18 Stations = x.Elements().Select((y, i) => new Station
19 {
20 Index = i,
21 Name = y.Attribute("Name").Value,
22 LineNo = x.Attribute("No").Value,
23 CanTransfer = y.Attribute("CanTransfer") == null ? false : bool.Parse(y.Attribute("CanTransfer").Value),
24 TransferNo = y.Attribute("TransferNo") == null ? null : y.Attribute("TransferNo").Value
25 }).ToList()
26 };
27 var translines = line.GetTransStations().Select(z => z.TransferNo.Split(',')).ToList();
28 foreach (var transline in translines)
29 {
30 foreach (var li in transline)
31 {
32 line.TransferLines.Add(li);
33 }
34 }
35 line.TransferLines = line.TransferLines.Distinct().ToList();
36 return line;
37 }).ToList();
38 }
3、分多种情况进行处理，核心代码：
1 /// <summary>
2 /// 获取地铁乘车信息
3 /// </summary>
4 /// <param name="depStation">出发站</param>
5 /// <param name="destStation">到达站</param>
6 /// <param name="city">所在城市</param>
7 /// <returns>返回各种换乘方案</returns>
8 public static List<QueryResult> GetRideSubwayInfo(string depStation, string destStation, CityEnum city)
9 {
10 InitSubwayLine(city);
11 if (string.IsNullOrWhiteSpace(depStation) || string.IsNullOrWhiteSpace(destStation)
12 || !AllSubwayLines.Exists(x => x.Stations.Exists(y => y.Name.Equals(depStation)))
13 || !AllSubwayLines.Exists(x => x.Stations.Exists(y => y.Name.Equals(destStation))))
14 return null;//出发站或到达站在线路上不存在！
15
16 //各种换乘提示
17 //同一条线路
18 var msg_oneline = "在{0}【{1}】上车，经过{2}站到达目的站【{3}】。\r\n具体线路为：\r\n(出发){4}(到达)\r\n总搭乘站点数：{5}\r\n";
19 //换乘1次
20 var msg_transOnce = "在{0}【{1}】上车，经过{2}站在【{3}】下车，换乘{4}，经过{5}站到达目的站【{6}】。\r\n具体线路为：\r\n(出发){7}(此处换乘{4})-->{8}(到达)\r\n总搭乘站点数：{9}\r\n";
21 //换乘2次
22 var msg_transTwice = "在{0}【{1}】上车，经过{2}站在【{3}】下车，换乘{4}，经过{5}站在【{6}】下车，换乘{7}，经过{8}站到达目的站【{9}】。\r\n具体线路为：\r\n(出发){10}(此处换乘{4})-->{11}(此处换乘{7})-->{12}(到达)\r\n总搭乘站点数：{13}\r\n";
23 //换乘3次
24 var msg_transThreetimes = "在{0}【{1}】上车，经过{2}站在【{3}】下车，换乘{4}，经过{5}站在【{6}】下车，换乘{7}，经过{8}站在【{9}】下车，换乘{10}，经过{11}站到达目的站【{12}】。"
25 + "\r\n具体线路为：\r\n(出发){13}(此处换乘{4})-->{14}(此处换乘{7})-->{15}(此处换乘{10})-->{16}(到达)\r\n总搭乘站点数：{17}\r\n";
26 //换乘4次
27 var msg_transFourtimes = "在{0}【{1}】上车，经过{2}站在【{3}】下车，换乘{4}，经过{5}站在【{6}】下车，换乘{7}，经过{8}站在【{9}】下车，换乘{10}，经过{11}站在【{12}】下车，换乘{13}，经过{14}站到达目的站【{15}】。"
28 + "\r\n具体线路为：\r\n(出发){16}(此处换乘{4})-->{17}(此处换乘{7})-->{18}(此处换乘{10})-->{19}(此处换乘{13})-->{20}(到达)\r\n总搭乘站点数：{21}\r\n";
29
30 //保存各种换乘方案
31 var result = new List<QueryResult>();
32 //第一步：先查找始发站和到达站在哪一条线路
33 var afterDepLines = GetAcrossLines(depStation);
34 var afterDestLines = GetAcrossLines(destStation);
35 //根据同一条线和不同线路展开分析
36 if (IsSameLine(depStation, destStation))
37 {
38 #region 同一条线路
39 var commLines = afterDepLines.Where(x => afterDestLines.Select(y => y.No).Contains(x.No)).ToList();
40 //判断线路是否相同，相同直接计算站点距离
41 var depIndex = GetIndexOnLine(depStation, commLines.First());
42 var destIndex = GetIndexOnLine(destStation, commLines.First());
43 var crossStations = commLines.First().Stations.Between(depIndex, destIndex).Select(x => x.Name).ToList();
44 var range = crossStations.Count - 1;
45 if (depIndex > destIndex) crossStations.Reverse();
46 var rs = msg_oneline.FormatTo(commLines.First().ToString(), depStation, range, destStation,
47 crossStations.ToJoinString(), range);
48 result.Add(new QueryResult() { Description = rs, Range = range });
49 #endregion
50 }
51 else
52 {
53 #region 不同线路
54 if (!IsTransferStation(depStation) && !IsTransferStation(destStation))//如果始发站和终点站都不是换乘站，则表示始发站和到达站都是只有一条线路通过
55 {
56 if (afterDepLines.First().IsIntersect(afterDestLines.First()))
57 {
58 #region 如果两条线路交叉，一定有换乘站点
59 var clist = GetAcrossStations(afterDepLines.First(), afterDestLines.First()).Select(x => x.Name).ToList();
60 var i = GetIndexOnLine(depStation, afterDepLines.First());
61 var j = GetIndexOnLine(clist.First(), afterDepLines.First());
62 var k = GetIndexOnLine(destStation, afterDestLines.First());
63 var l = GetIndexOnLine(clist.First(), afterDestLines.First());
64 var coss1 = afterDepLines.First().Stations.Between(i, j).Select(x => x.Name).ToList();
65 var coss2 = afterDestLines.First().Stations.Between(k, l).Select(x => x.Name).ToList();
66 if (i > j) coss1.Reverse();
67 if (k < l) coss2.Reverse();
68 var rang1 = coss1.Count - 1;
69 var rang2 = coss2.Count - 1;
70 var h = rang1 + rang2; //站点数
71 var rs = msg_transOnce.FormatTo(afterDepLines.First().ToString(), depStation, rang1, clist.First(),
72 afterDestLines.First().ToString(), rang2, destStation,
73 coss1.ToJoinString(), coss2.Where(x => x != clist.First()).ToJoinString(), h);
74 result.Add(new QueryResult()
75 {
76 Description = rs,
77 Range = h,
78 TransferStations = new List<string>() { clist.First() },
79 TransferTimes = 1
80 });
81 #endregion
82 }
83 else
84 {
85 #region 不交叉，需要通过第三条线路换乘，即多次换乘
86 var depSta = GetStation(depStation);
87 var destSta = GetStation(destStation);
88 //找出两条线路的可换乘站点，找出可换乘相同线路的站点
89 var trans1 = afterDepLines.First().GetTransStations();
90 var trans2 = afterDestLines.First().GetTransStations();
91 var trans3 = new List<Station>();
92 var trans4 = new List<Station>();
93 var expets = trans1.Join(trans2, x => x.TransferNo, y => y.TransferNo, (x, y) =>
94 {
95 trans3.Add(x);
96 trans4.Add(y);
97 return x.Name + "---" + y.Name;
98 }).ToList();
99 if (expets.Any())
100 {
101 #region 两次换乘
102 //trans3.Count和trans4.Count必定相等
103 //计算最短距离，列出所有换乘方案
104 for (var i = 0; i < trans3.Count; i++)
105 {
106 var tranLine = GetLine(trans3[i].TransferNo);
107 //获取这两个站点在此线路的索引
108 var ix1 = depSta.Index;
109 var ix2 = destSta.Index;
110 var iix1 = GetIndexOnLine(trans3[i].Name, depSta.LineNo);
111 var iix2 = GetIndexOnLine(trans4[i].Name, destSta.LineNo);
112 var tx1 = GetIndexOnLine(trans3[i].Name, tranLine);
113 var tx2 = GetIndexOnLine(trans4[i].Name, tranLine);
114
115 var depRange = afterDepLines.First().Stations.Between(ix1, iix1).Select(x => x.Name).ToList();
116 var destRange = afterDestLines.First().Stations.Between(ix2, iix2).Select(x => x.Name).ToList();
117 var transRange = tranLine.Stations.Between(tx1, tx2).Select(x => x.Name).ToList();
118 if (ix1 > iix1) depRange.Reverse();
119 if (ix2 < iix2) destRange.Reverse();
120 if (tx1 > tx2) transRange.Reverse();
121 var r1 = depRange.Count - 1;
122 var r2 = destRange.Count - 1;
123 var r3 = transRange.Count - 1;
124 var r = r1 + r2 + r3;
125 var rs = msg_transTwice.FormatTo(afterDepLines.First().ToString(), depStation, r1,
126 trans3[i].Name,
127 tranLine.ToString(), r3, trans4[i].Name, afterDestLines.First().ToString(), r2,
128 destStation, depRange.ToJoinString(),
129 transRange.Where(x => !x.IsSame(trans3[i].Name) && !x.IsSame(trans4[i].Name)).ToJoinString(),
130 destRange.ToJoinString(), r);
131 result.Add(new QueryResult()
132 {
133 Description = rs,
134 Range = r,
135 TransferTimes = 2,
136 TransferStations = new List<string>() { trans3[i].Name, trans4[i].Name }
137 });
138 }
139 #endregion
140 }
141 #region 查找3次以上换乘的可能结果，寻求最短距离
142 var trlines1 = afterDepLines.First().TransferLines.Select(GetLine).ToList();
143 var trlines2 = afterDestLines.First().TransferLines.Select(GetLine).ToList();
144 var destss = new List<Station>();
145
146 #region 换乘3次
147 foreach (var depline in trlines1)
148 {
149 foreach (var destline in trlines2)
150 {
151 var ss = destline.GetAcrossStations(depline);
152 if (!ss.Any()) continue; //3次换乘
153 var slist1 = afterDepLines.First().GetAcrossStations(depline);
154 if (!slist1.Any()) continue;
155 var s1 = slist1.GetClosestStation(depSta.Name);
156 var s1_ix1 = depSta.Index;
157 var s1_ix2 = s1.Index;
158 var s1_range =
159 afterDepLines.First()
160 .Stations.Between(s1_ix1, s1_ix2)
161 .Select(x => x.Name)
162 .ToList();
163 var s1_h = s1_range.Count - 1;
164 if (s1_ix1 > s1_ix2) s1_range.Reverse();
165
166 var s2_ix1 = GetIndexOnLine(s1.Name, depline);
167 var s2_ix2 = GetIndexOnLine(ss.First().Name, depline);
168 var s2_range = depline.Stations.Between(s2_ix1, s2_ix2).Select(x => x.Name).ToList();
169 var s2_h = s2_range.Count - 1;
170 if (s2_ix1 > s2_ix2) s2_range.Reverse();
171
172 var slist3 = destline.GetAcrossStations(afterDestLines.First());
173 if (!slist3.Any()) continue;
174 var s3 = slist3.GetClosestStation(ss.First().Name);
175 var s3_ix1 = s3.Index;
176 var s3_ix2 = ss.First().Index;
177 var s3_range = destline.Stations.Between(s3_ix1, s3_ix2).Select(x => x.Name).ToList();
178 var s3_h = s3_range.Count - 1;
179 if (s3_ix1 < s3_ix2) s3_range.Reverse();
180
181 var s4_ix1 = GetIndexOnLine(s3.Name, afterDestLines.First());
182 var s4_ix2 = destSta.Index;
183 var s4_range =
184 afterDestLines.First()
185 .Stations.Between(s4_ix1, s4_ix2)
186 .Select(x => x.Name)
187 .ToList();
188 var s4_h = s4_range.Count - 1;
189 if (s4_ix1 > s4_ix2) s4_range.Reverse();
190
191 var h = s1_h + s2_h + s3_h + s4_h;
192 var rs = msg_transThreetimes.FormatTo(afterDepLines.First().ToString(), depStation,
193 s1_h, s1.Name,
194 depline.ToString(), s2_h, ss.First().Name,
195 GetLine(ss.First().LineNo).ToString(), s3_h, s3.Name,
196 afterDestLines.First().ToString(), s4_h, destStation, s1_range.ToJoinString(),
197 s2_range.Where(x => x != s1.Name).ToJoinString(),
198 s3_range.Where(x => x != ss.First().Name).ToJoinString(),
199 s4_range.Where(x => x != s3.Name).ToJoinString(), h);
200 result.Add(new QueryResult()
201 {
202 Description = rs,
203 Range = h,
204 TransferTimes = 3,
205 TransferStations =
206 new List<string>()
207 {
208 s1.Name,
209 ss.First().Name,
210 s3.Name
211 }
212 });
213 destss.AddRange(ss);
214 }
215 }
216 #endregion
217
218 if (!destss.Any()) //换乘4次
219 {
220 #region 换乘4次
221 foreach (var depline in trlines1)
222 {
223 foreach (var destline in trlines2)
224 {
225 var deptrlines =
226 depline.TransferLines.Where(x => x != afterDepLines.First().No)
227 .Select(GetLine)
228 .ToList();
229 foreach (var line in deptrlines)
230 {
231 var s1 = line.GetAcrossStations(destline);
232 if (!s1.Any()) continue; //4次换乘
233 var trlist1 = afterDepLines.First().GetAcrossStations(depline);
234 if (!trlist1.Any()) continue;
235 var tr1 = trlist1.GetClosestStation(depSta.Name);
236 var s1_ix1 = depSta.Index;
237 var s1_ix2 = tr1.Index;
238 var s1_range =
239 afterDepLines.First()
240 .Stations.Between(s1_ix1, s1_ix2)
241 .Select(x => x.Name)
242 .ToList();
243 var h1 = s1_range.Count - 1;
244 if (s1_ix1 > s1_ix2) s1_range.Reverse();
245
246 var trlist2 = GetLine(tr1.TransferNo).GetAcrossStations(line);
247 if (!trlist2.Any()) continue;
248 var tr2 = trlist2.GetClosestStation(tr1.Name);
249 var s2_ix1 = GetIndexOnLine(tr1.Name, depline);
250 var s2_ix2 = tr2.Index;
251 var s2_range =
252 depline.Stations.Between(s2_ix1, s2_ix2)
253 .Select(x => x.Name)
254 .ToList();
255 var h2 = s2_range.Count - 1;
256 if (s2_ix1 > s2_ix2) s2_range.Reverse();
257
258 var s3_ix1 = GetIndexOnLine(tr2.Name, line);
259 var s3_ix2 = s1.First().Index;
260 var s3_range =
261 line.Stations.Between(s3_ix1, s3_ix2)
262 .Select(x => x.Name)
263 .ToList();
264 var h3 = s3_range.Count - 1;
265 if (s3_ix1 > s3_ix2) s3_range.Reverse();
266
267 var trlist3 = destline.GetAcrossStations(afterDestLines.First());
268 if (!trlist3.Any()) continue;
269 var tr3 = trlist3.GetClosestStation(s1.First().Name);
270 var s4_ix1 = GetIndexOnLine(s1.First().Name, destline);
271 var s4_ix2 = tr3.Index;
272 var s4_range =
273 destline.Stations.Between(s4_ix1, s4_ix2)
274 .Select(x => x.Name)
275 .ToList();
276 var h4 = s4_range.Count - 1;
277 if (s4_ix1 > s4_ix2) s4_range.Reverse();
278
279 var s5_ix1 = GetIndexOnLine(tr3.Name, afterDestLines.First());
280 var s5_ix2 = destSta.Index;
281 var s5_range =
282 afterDestLines.First()
283 .Stations.Between(s5_ix1, s5_ix2)
284 .Select(x => x.Name)
285 .ToList();
286 var h5 = s5_range.Count - 1;
287 if (s5_ix1 > s5_ix2) s5_range.Reverse();
288 var h = h1 + h2 + h3 + h4 + h5;
289 var rs =
290 msg_transFourtimes.FormatTo(afterDepLines.First().ToString(),
291 depStation, h1, tr1.Name,
292 depline.ToString(), h2, tr2.Name,
293 line.ToString(), h3, s1.First().Name,
294 destline.ToString(), h4, tr3.Name,
295 afterDestLines.First().ToString(), h5, destStation,
296 s1_range.ToJoinString(),
297 s2_range.Where(x => x != tr1.Name).ToJoinString(),
298 s3_range.Where(x => x != tr2.Name).ToJoinString(),
299 s4_range.Where(x => x != tr2.Name && x != s1.First().Name).ToJoinString(),
300 s5_range.Where(x => x != tr3.Name).ToJoinString(), h);
301 result.Add(new QueryResult()
302 {
303 Description = rs,
304 Range = h,
305 TransferTimes = 4,
306 TransferStations =
307 new List<string>()
308 {
309 tr1.Name,
310 tr2.Name,
311 s1.First().Name,
312 tr3.Name
313 }
314 });
315 destss.AddRange(s1);
316 }
317 }
318 }
319 #endregion
320 }
321 if (!destss.Any())//换乘4次以上
322 {
323
324 }
325 #endregion
326 #endregion
327 }
328 }
329 else //始发站和到达站有其中一个是换乘站
330 {
331 //找出到达站经过的路线和始发站所在路线的交叉线路
332 var crossLines = GetAcrossLines(depStation, destStation);
333 //分三种情况：1、始发站不是换乘站而到达站是换乘站；2、始发站是换乘站而到达站不是换乘站；3、始发站和到达站都是换乘站，根据情况展开分析
334 if (!IsTransferStation(depStation) && IsTransferStation(destStation))
335 {
336 #region 情况1：始发站不是换乘站而到达站是换乘站
337 if (crossLines.Count > 0) //依赖交叉线
338 {
339 var listTrans = new List<Station>();
340 foreach (var line in crossLines)
341 {
342 //找出每条交叉线换乘到始发站线路的所有换乘站
343 var ss = line.GetTransStations()
344 .Where(x => x.TransferNo.IsSame(afterDepLines.First().No))
345 .ToList();
346 listTrans.AddRange(ss);
347 }
348 var depIx = GetIndexOnLine(depStation, afterDepLines.First());
349 var tranStas =
350 listTrans.Select(
351 s => new { sta = s, ix = GetIndexOnLine(s.Name, afterDepLines.First()) })
352 .ToList();
353 foreach (var sta in tranStas)
354 {
355 var destIx = GetIndexOnLine(destStation, sta.sta.LineNo);
356 var tranIx = GetIndexOnLine(sta.sta.Name, sta.sta.LineNo);
357 var coss1 =
358 afterDepLines.First()
359 .Stations.Between(depIx, sta.ix)
360 .Select(x => x.Name)
361 .ToList();
362 var coss2 =
363 GetLine(sta.sta.LineNo)
364 .Stations.Between(destIx, tranIx)
365 .Select(x => x.Name)
366 .ToList();
367 var rang1 = coss1.Count - 1;
368 var rang2 = coss2.Count - 1;
369 var h = rang1 + rang2; //站点数
370 if (depIx > sta.ix) coss1.Reverse();
371 if (destIx < tranIx) coss2.Reverse();
372
373 var rs = msg_transOnce.FormatTo(afterDepLines.First().ToString(), depStation, rang1,
374 sta.sta.Name,
375 GetLine(sta.sta.LineNo).ToString(), rang2, destStation,
376 coss1.ToJoinString(), coss2.Where(x => x != sta.sta.Name).ToJoinString(), h);
377 result.Add(new QueryResult()
378 {
379 Description = rs,
380 Range = h,
381 TransferTimes = 1,
382 TransferStations = new List<string>() { sta.sta.Name }
383 });
384 }
385 }
386 //查找其他换乘可能
387 var depSta = GetStation(depStation);
388 var trlinesDep = afterDepLines.First().TransferLines.Select(GetLine).ToList();
389 foreach (var depline in afterDestLines)
390 {
391 var trlineItems = depline.TransferLines.Select(GetLine).ToList();
392 foreach (var iline in trlineItems)
393 {
394 foreach (var destline in trlinesDep)
395 {
396 var ss = destline.GetAcrossStations(iline);
397 if (!ss.Any()) continue; //3次换乘
398 var slist1 = afterDepLines.First().GetAcrossStations(destline);
399 if (!slist1.Any()) continue;
400 var s1 = slist1.GetClosestStation(depStation);
401 var s1_ix1 = depSta.Index;
402 var s1_ix2 = s1.Index;
403
404 var s1_range =
405 afterDepLines.First()
406 .Stations.Between(s1_ix1, s1_ix2)
407 .Select(x => x.Name)
408 .ToList();
409 var s1_h = s1_range.Count - 1;
410 if (s1_ix1 > s1_ix2) s1_range.Reverse();
411
412 var s2 = ss.GetClosestStation(s1.Name);
413 var s2_ix1 = GetIndexOnLine(s1.Name, destline);
414 var s2_ix2 = GetIndexOnLine(s2.Name, destline);
415 var s2_range = destline.Stations.Between(s2_ix1, s2_ix2).Select(x => x.Name).ToList();
416 var s2_h = s2_range.Count - 1;
417 if (s2_ix1 > s2_ix2) s2_range.Reverse();
418
419 var slist3 = iline.GetAcrossStations(depline);
420 if (!slist3.Any()) continue;
421 var s3 = slist3.GetClosestStation(s2.Name);
422 var s3_ix1 = s3.Index;
423 var s3_ix2 = GetIndexOnLine(s2.Name, iline);
424 var s3_range = iline.Stations.Between(s3_ix1, s3_ix2).Select(x => x.Name).ToList();
425 var s3_h = s3_range.Count - 1;
426 if (s3_ix1 < s3_ix2) s3_range.Reverse();
427
428 var s4_ix1 = GetIndexOnLine(s3.Name, depline);
429 var s4_ix2 = GetIndexOnLine(destStation, depline);
430 var s4_range = depline.Stations.Between(s4_ix1, s4_ix2)
431 .Select(x => x.Name)
432 .ToList();
433 var s4_h = s4_range.Count - 1;
434 if (s4_ix1 > s4_ix2) s4_range.Reverse();
435
436 var h = s1_h + s2_h + s3_h + s4_h;
437 if (s2_h == 0 || s3_h == 0 || s4_h == 0 || destline.No.IsSame(iline.No)) continue;
438 var rs = msg_transThreetimes.FormatTo(afterDepLines.First().ToString(),
439 depStation,
440 s1_h, s1.Name,
441 destline.ToString(), s2_h, s2.Name,
442 iline.ToString(), s3_h, s3.Name,
443 depline.ToString(), s4_h, destStation, s1_range.ToJoinString(),
444 s2_range.Where(x => x != s1.Name).ToJoinString(),
445 s3_range.Where(x => x != s2.Name).ToJoinString(),
446 s4_range.Where(x => x != s3.Name).ToJoinString(), h);
447 result.Add(new QueryResult()
448 {
449 Description = rs,
450 Range = h,
451 TransferTimes = 3,
452 TransferStations =
453 new List<string>()
454 {
455 s1.Name,
456 s2.Name,
457 s3.Name
458 }
459 });
460 }
461 }
462 }
463 #endregion
464 }
465 if (IsTransferStation(depStation) && !IsTransferStation(destStation))
466 {
467 #region 情况2：始发站是换乘站而到达站不是换乘站
468 var transLines =
469 afterDepLines.Where(
470 x =>
471 x.Stations.Exists(
472 y => y.CanTransfer && y.TransferNo.Contains(afterDestLines.First().No)))
473 .ToList();
474 if (transLines.Any())
475 {
476 var clist =
477 GetAcrossStations(transLines.First(), afterDestLines.First())
478 .Select(x => x.Name)
479 .ToList();
480 var i = GetIndexOnLine(depStation, transLines.First());
481 var j = GetIndexOnLine(clist.First(), transLines.First());
482 var k = GetIndexOnLine(destStation, afterDestLines.First());
483 var l = GetIndexOnLine(clist.First(), afterDestLines.First());
484 var coss1 = transLines.First().Stations.Between(i, j).Select(x => x.Name).ToList();
485 var coss2 = afterDestLines.First().Stations.Between(k, l).Select(x => x.Name).ToList();
486 var rang1 = coss1.Count - 1;
487 var rang2 = coss2.Count - 1;
488 var h = rang1 + rang2; //站点数
489 if (i > j) coss1.Reverse();
490 if (k < l) coss2.Reverse();
491
492 var rs = msg_transOnce.FormatTo(transLines.First().ToString(), depStation, rang1,
493 clist.First(),
494 afterDestLines.First().ToString(), rang2, destStation,
495 coss1.ToJoinString(), coss2.Where(x => x != clist.First()).ToJoinString(), h);
496 result.Add(new QueryResult()
497 {
498 Description = rs,
499 Range = h,
500 TransferTimes = 1,
501 TransferStations = new List<string>() { clist.First() }
502 });
503 }
504 //寻找其他换乘可能
505 var destSta = GetStation(destStation);
506 var trlinesDest = afterDestLines.First().TransferLines.Select(GetLine).ToList();
507 foreach (var depline in afterDepLines)
508 {
509 var trlineItems = depline.TransferLines.Select(GetLine).ToList();
510 foreach (var iline in trlineItems)
511 {
512 foreach (var destline in trlinesDest)
513 {
514 var ss = iline.GetAcrossStations(destline);
515 if (!ss.Any()) continue; //3次换乘
516 var slist1 = depline.GetAcrossStations(iline);
517 if (!slist1.Any()) continue;
518 var s1 = slist1.GetClosestStation(depStation);
519 var s1_ix1 = GetIndexOnLine(depStation, depline);
520 var s1_ix2 = s1.Index;
521 var s1_range =
522 depline.Stations.Between(s1_ix1, s1_ix2)
523 .Select(x => x.Name)
524 .ToList();
525 var s1_h = s1_range.Count - 1;
526 if (s1_ix1 > s1_ix2) s1_range.Reverse();
527
528 var s2 = ss.GetClosestStation(s1.Name);
529 var s2_ix1 = GetIndexOnLine(s1.Name, iline);
530 var s2_ix2 = GetIndexOnLine(s2.Name, iline);
531 var s2_range = iline.Stations.Between(s2_ix1, s2_ix2).Select(x => x.Name).ToList();
532 var s2_h = s2_range.Count - 1;
533 if (s2_ix1 > s2_ix2) s2_range.Reverse();
534
535 var slist3 = destline.GetAcrossStations(afterDestLines.First());
536 if (!slist3.Any()) continue;
537 var s3 = slist3.GetClosestStation(ss.First().Name);
538 var s3_ix1 = s3.Index;
539 var s3_ix2 = GetIndexOnLine(s2.Name, destline);
540 var s3_range = destline.Stations.Between(s3_ix1, s3_ix2).Select(x => x.Name).ToList();
541 var s3_h = s3_range.Count - 1;
542 if (s3_ix1 < s3_ix2) s3_range.Reverse();
543
544 var s4_ix1 = GetIndexOnLine(s3.Name, afterDestLines.First());
545 var s4_ix2 = destSta.Index;
546 var s4_range =
547 afterDestLines.First()
548 .Stations.Between(s4_ix1, s4_ix2)
549 .Select(x => x.Name)
550 .ToList();
551 var s4_h = s4_range.Count - 1;
552 if (s4_ix1 > s4_ix2) s4_range.Reverse();
553
554 var h = s1_h + s2_h + s3_h + s4_h;
555 if (s1_h == 0 || s2_h == 0 || s3_h == 0 || iline.No.IsSame(destline.No)) continue;
556 var rs = msg_transThreetimes.FormatTo(depline.ToString(), depStation,
557 s1_h, s1.Name,
558 iline.ToString(), s2_h, s2.Name,
559 destline.ToString(), s3_h, s3.Name,
560 afterDestLines.First().ToString(), s4_h, destStation,
561 s1_range.ToJoinString(),
562 s2_range.Where(x => x != s1.Name).ToJoinString(),
563 s3_range.Where(x => x != s2.Name).ToJoinString(),
564 s4_range.Where(x => x != s3.Name).ToJoinString(), h);
565 result.Add(new QueryResult()
566 {
567 Description = rs,
568 Range = h,
569 TransferTimes = 3,
570 TransferStations =
571 new List<string>()
572 {
573 s1.Name,
574 s2.Name,
575 s3.Name
576 }
577 });
578 }
579 }
580 }
581 #endregion
582 }
583 if (IsTransferStation(depStation) && IsTransferStation(destStation))
584 {
585 #region 情况3：始发站和到达站都是换乘站
586 if (crossLines.Count > 0) //依赖交叉线
587 {
588 var transStations = GetClosestStation(depStation, true);
589 if (
590 !transStations.Exists(
591 x =>
592 crossLines.Exists(y => y.Stations.Exists(z => x.TransferNo.Split(',').Intersect(z.LineNo.Split(',')).Any()))))
593 {
594 transStations = new List<Station>();
595 afterDepLines.ForEach(x =>
596 {
597 var ctrans = x.GetTransStations();
598 var ctrans2 =
599 ctrans.Where(
600 y =>
601 crossLines.Exists(
602 z => z.Stations.Exists(zz => y.TransferNo.Split(',').Intersect(zz.LineNo.Split(',')).Any())))
603 .ToList();
604 transStations.AddRange(ctrans2);
605 });
606 }
607 var transLine =
608 afterDestLines.Where(
609 x =>
610 x.Stations.Exists(y => transStations.Exists(z => z.Name.IsSame(y.Name))))
611 .ToList();
612 var intersStas =
613 transStations.Where(
614 x =>
615 transLine.Exists(
616 y =>
617 y.Stations.Exists(
618 z => z.Name.IsSame(x.Name) && x.TransferNo.Split(',').Intersect(z.LineNo.Split(',')).Any())))
619 .ToList();
620 foreach (var line in transLine)
621 {
622 //分别获取换乘站在换乘线上的索引
623 foreach (var t in intersStas)
624 {
625 var ix = GetIndexOnLine(destStation, line); //目的站在换乘线上的索引
626 var iix = GetIndexOnLine(t.Name, line); //换乘站在换乘线上的索引
627 if (iix == -1) continue;
628 var ix2 = GetIndexOnLine(depStation, t.LineNo); //始发站在换乘站所在线路上的索引
629 var iix2 = GetIndexOnLine(t.Name, t.LineNo); //换乘站在始发站所在线路上的索引
630
631 var ixRange = line.Stations.Between(ix, iix).Select(x => x.Name).ToList();
632 var ixRange2 = GetLine(t.LineNo).Stations.Between(ix2, iix2).Select(x => x.Name).ToList();
633 var ixh = ixRange.Count - 1;
634 var ixh2 = ixRange2.Count - 1;
635 var h = ixh + ixh2;
636 if (ix < iix) ixRange.Reverse();
637 if (ix2 > iix2) ixRange2.Reverse();
638 var rs = msg_transOnce.FormatTo(GetLine(t.LineNo).ToString(), depStation, ixh2, t.Name,
639 line.ToString(), ixh, destStation,
640 ixRange2.ToJoinString(),
641 ixRange.Where(x => !x.IsSame(t.Name)).ToJoinString(), h);
642 result.Add(new QueryResult()
643 {
644 Description = rs,
645 Range = h,
646 TransferTimes = 1,
647 TransferStations = new List<string>() { t.Name }
648 });
649 }
650 }
651 }
652 #endregion
653 }
654 }
655 #endregion
656 }
657
658 //查找其他可能性
659 #region 深度挖掘其他方案
660 //找出经过始发站和到达站的线路中共同穿过的公共线路，寻找换乘方案
661 var connLines = GetCommonLines(depStation, destStation);
662 if (connLines.Count > 0)
663 {
664 var transDep = new List<Station>();
665 var transDest = new List<Station>();
666 foreach (var depLine in afterDepLines)
667 {
668 //在经过始发站的线路中的站点中找到可换乘到公共线路的站点
669 var trans = depLine.GetTransStations()
670 .Where(x => x.Name != depStation && x.Name != destStation && connLines.Exists(y => x.TransferNo.Contains(y.No)))
671 .ToList();
672 transDep.AddRange(trans);
673 }
674 foreach (var destLine in afterDestLines)
675 {
676 //在经过到达站的线路中的站点中找到可换乘到公共线路的站点
677 var trans = destLine.GetTransStations()
678 .Where(x => x.Name != depStation && x.Name != destStation && connLines.Exists(y => x.TransferNo.Contains(y.No)))
679 .ToList();
680 transDest.AddRange(trans);
681 }
682 foreach (var d1 in transDep)
683 {
684 foreach (var d2 in transDest)
685 {
686 //找出交叉站点，即可换乘同一条公共线路的站点
687 var inters = d1.TransferNo.Split(',').Intersect(d2.TransferNo.Split(',')).ToList();
688 if (!inters.Any() || d1.Name.IsSame(d2.Name)) continue;
689 var tranLine = GetLine(inters.First());
690 var depLine = GetLine(d1.LineNo);
691 var destLine = GetLine(d2.LineNo);
692 var ix1 = GetIndexOnLine(depStation, depLine);
693 var ix2 = GetIndexOnLine(d1.Name, depLine);
694 var iix1 = GetIndexOnLine(d1.Name, tranLine);
695 var iix2 = GetIndexOnLine(d2.Name, tranLine);
696 var iiix1 = GetIndexOnLine(d2.Name, destLine);
697 var iiix2 = GetIndexOnLine(destStation, destLine);
698
699 var depRange = depLine.Stations.Between(ix1, ix2).Select(x => x.Name).ToList();
700 var transRange = tranLine.Stations.Between(iix1, iix2).Select(x => x.Name).ToList();
701 var destRange = destLine.Stations.Between(iiix1, iiix2).Select(x => x.Name).ToList();
702 var r1 = depRange.Count - 1;
703 var r2 = transRange.Count - 1;
704 var r3 = destRange.Count - 1;
705 var r = r1 + r2 + r3;
706 if (ix1 > ix2) depRange.Reverse();
707 if (iix1 > iix2) transRange.Reverse();
708 if (iiix1 > iiix2) destRange.Reverse();
709 string rs;
710 if (r1 > 0 && r2 > 0 && r3 > 0)
711 {
712 rs = msg_transTwice.FormatTo(depLine.ToString(), depStation, r1, d1.Name, tranLine.ToString(), r2,
713 d2.Name, destLine.ToString(), r3, destStation, depRange.ToJoinString(),
714 transRange.Where(x => !x.IsSame(d1.Name)).ToJoinString(),
715 destRange.Where(x => !x.IsSame(d1.Name) && !x.IsSame(d2.Name)).ToJoinString(), r);
716 result.Add(new QueryResult()
717 {
718 Description = rs,
719 Range = r,
720 TransferTimes = 2,
721 TransferStations = new List<string>() { d1.Name, d2.Name }
722 });
723 }
724 else if (r1 > 0 && r2 == 0 && r3 > 0)
725 {
726 rs = msg_transOnce.FormatTo(GetLine(inters.First()).ToString(), depStation, r1, d2.Name,
727 destLine.ToString(), r3, destStation,
728 depRange.ToJoinString(),
729 destRange.Where(x => !x.IsSame(d2.Name)).ToJoinString(), r);
730 result.Add(new QueryResult()
731 {
732 Description = rs,
733 Range = r,
734 TransferTimes = 1,
735 TransferStations = new List<string>() { d2.Name }
736 });
737 }
738 else
739 {
740 rs = msg_transOnce.FormatTo(depLine.ToString(), depStation, r1, d1.Name, tranLine.ToString(), r2,
741 destStation, depRange.ToJoinString(),
742 transRange.Where(x => !x.IsSame(d1.Name)).ToJoinString(), r);
743 result.Add(new QueryResult()
744 {
745 Description = rs,
746 Range = r,
747 TransferTimes = 1,
748 TransferStations = new List<string>() { d1.Name }
749 });
750 }
751 }
752 }
753 }
754 #endregion
755
756 //重新组织数据
757 result.ForEach(x =>
758 {
759 var desc = x.Description.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
760 x.Suggestion = desc[0];
761 x.Route = desc[2];
762 });
763 //去除重复方案，保留一个
764 var gyResult = result.GroupBy(x => x.Route).Select(x => x.First()).ToList();
765 //移除逗逼方案，例如：A-B-A-C
766 gyResult.RemoveAll(x => x.Route.Split(new string[] { depStation }, StringSplitOptions.RemoveEmptyEntries).Length > 2
767 || x.Route.Split(new string[] { destStation }, StringSplitOptions.RemoveEmptyEntries).Length > 2);
768 return gyResult;
769 }
因为只做了北京、上海、深圳、广州四个城市的站点数据，所以演示只能查询这四个城市的地铁换乘，大家可以补充自己想要的城市的地铁数据，格式请参照源码中上面四个城市的xml格式。
最后附上源码地址，https://gitee.com/herubin/subway_transfer_query_tool
参数说明：dep为始发站，dest为到达站，city为所在城市拼音，这个是专门为其他程序调用开放的接口
我在我的小博客也发布了：http://www.xiaoboke.net/admin/blog/article/26
有兴趣的朋友可以看看，欢迎大家提出改进意见，码个代码不容易，各位大哥大姐的点赞是我不断努力的动力
，谢谢！