设计一个长沙地铁线路查询系统,为长沙地铁乘客咨询从任一个站点到另一个站点之间的最短路径问题。并生成代码
时间: 2024-04-06 17:30:52 浏览: 80
以下是一个使用 Python 实现的长沙地铁线路查询系统的示例代码。该代码使用了 Dijkstra 算法来计算最短路径。
```python
import heapq
# 定义地铁站点和线路
stations = [
'岳麓区政府',
'岳麓大道',
'望月湖',
'湖南大学',
'枫林路',
'银盆岭',
'梅溪湖'
]
lines = {
'1号线': ['岳麓区政府', '岳麓大道', '望月湖', '湖南大学', '枫林路', '银盆岭', '梅溪湖']
}
# 定义邻接列表
subway = {
'岳麓区政府': {'岳麓大道': 0.5},
'岳麓大道': {'岳麓区政府': 0.5, '望月湖': 0.8},
'望月湖': {'岳麓大道': 0.8, '湖南大学': 0.6},
'湖南大学': {'望月湖': 0.6, '枫林路': 1.0},
'枫林路': {'湖南大学': 1.0, '银盆岭': 1.2},
'银盆岭': {'枫林路': 1.2, '梅溪湖': 1.5},
'梅溪湖': {'银盆岭': 1.5}
}
def dijkstra(graph, start, end):
# 初始化距离和父节点
distances = {start: 0}
parents = {start: None}
# 初始化优先队列
queue = [(0, start)]
while queue:
# 取出当前距离最短的站点
current_distance, current_node = heapq.heappop(queue)
# 如果当前站点已经是终点,则返回最短路径
if current_node == end:
path = []
while current_node:
path.append(current_node)
current_node = parents[current_node]
path.reverse()
return path, distances[end]
# 遍历当前站点的邻居
for neighbor, distance in graph[current_node].items():
# 计算通过当前站点到达邻居的距离
new_distance = current_distance + distance
# 如果比之前记录的距离更短,则更新距离和父节点
if neighbor not in distances or new_distance < distances[neighbor]:
distances[neighbor] = new_distance
parents[neighbor] = current_node
heapq.heappush(queue, (new_distance, neighbor))
# 如果无法到达终点,则返回空路径和无穷大的距离
return [], float('inf')
# 定义查询函数
def query(start, end):
if start not in stations or end not in stations:
print('输入站点不存在,请重新输入。')
return
path, distance = dijkstra(subway, start, end)
if not path:
print('无法到达目的地,请重新输入。')
return
print(f'从{start}到{end}的最短路径是:')
for i in range(len(path) - 1):
line = None
for l, s in lines.items():
if path[i] in s and path[i + 1] in s:
line = l
break
print(f'{i + 1}. {path[i]}({line}) ->')
print(f'{len(path)}. {path[-1]}')
# 示例:从岳麓区政府到梅溪湖的最短路径
query('岳麓区政府', '梅溪湖')
```
在以上代码中,我们首先定义了长沙地铁的站点和线路。然后,我们将地铁线路建立为邻接列表 `subway`,其中每个站点对应一个字典,字典的键是邻居站点名,值是到邻居站点的距离。接着,我们实现了 `dijkstra` 函数来计算最短路径,该函数的输入参数为邻接列表、起点和终点,输出结果为最短路径和距离。在该函数中,我们使用了一个 `distances` 字典来记录每个站点到起点的距离,使用一个 `parents` 字典来记录每个站点的父节点,使用一个优先队列 `queue` 来存储当前距离最短的站点。在每次循环中,我们从优先队列中取出当前距离最短的站点,然后遍历其邻居,更新邻居的距离和父节点。如果当前站点已经是终点,则返回最短路径。如果无法到达终点,则返回空路径和无穷大的距离。
最后,我们定义了 `query` 函数来实现查询功能。该函数首先检查输入的起点和终点是否存在,如果不存在则提示用户重新输入。然后,调用 `dijkstra` 函数来计算最短路径,并将最短路径按照站点顺序输出。在输出时,我们还根据站点所在的线路来显示线路信息。
阅读全文