主要功能
提供一副地铁线路图,计算指定两站之间最短(最少经过站数)乘车路线;输出指定地铁线路的所有站点。以北京地铁为例,地铁线路信息保存在地铁线路信息.txt中,格式如下:
地铁线路总数
线路名1 站名1 站名2 站名3 ...
线路名2 站名1 站名2 站名3 ...
线路名3 站名1 站名2 站名3 ......
实现语言
python
实现算法
BFS
类职责划分
ReadFile(file_name):读入地铁信息
build_subway(**lines):构建图结构
shortest_path(start, goal):用BFS找最短路径
核心代码
数据读入:
def ReadFile(file_name):
data=dict()
with open(file_name, "rt", encoding="utf-8") as file:
n=int(file.readline())
for i in range(n):
value=""
line=file.readline().split()
for i in line[1:]:
value=value+i+" "
data[line[0]]=value
return data
构建图结构:
def BuildMap(**lines):
for key in lines.keys():
value = lines[key]
lines[key] = value.split()
stations = set()
for key in lines.keys():
stations.update(set(lines[key]))
system = {}
for station in stations:
next_station = {}
for key in lines:
if station in lines[key]:
line = lines[key]
idx = line.index(station)
if idx == 0:
next_station[line[1]] = key
elif idx == len(line)-1:
next_station[line[idx-1]]=key
else:
next_station[line[idx-1]] = key
next_station[line[idx+1]] = key
system[station] = next_station
return system
处理环路:
def DealCircle(BJ_Subway): #发现环路时将其头尾相连
BJ_Subway[u'西直门'][u'积水潭'] = '二号线'
BJ_Subway[u'积水潭'][u'西直门'] = '二号线'
BJ_Subway[u'劲松'][u'潘家园'] = '十号线'
BJ_Subway[u'潘家园'][u'劲松'] = '十号线'
return BJ_Subway
fin_subway = DealCircle(tmp)
用BFS找最短路径:
def FindPath(start, goal):
if start == goal:
return [start]
explored = set()
queue = [ [start, ('',0)]]
while queue:
path = queue.pop(0)
s = path[-2]
linenum,changetimes = path[-1]#增加判断换乘的元组,linenum表示上一次的线路,changetimes表示
if s == goal:
return path
for state, action in fin_subway[s].items():
if state not in explored:
linechange = changetimes
explored.add(state)
if linenum != action:
linechange += 1
path2 = path[:-1] + [action, state, (action, linechange)]
queue.append(path2)
queue.sort(key=lambda path:path[-1][-1])
return []
测试用例
两站
换乘站到换乘站
代码已上传至github:https://github.com/QQQy120/Subway.git
总结
通过这次的作业我深刻认识到自己能力的不足,对于知识掌握的不熟练,不理解。
第一次使用博客园写作业,对于专业能力有了全新的认识。