有关于这个问题的完整代码吗
时间: 2024-04-06 07:30:56 浏览: 24
这里给出一个使用 Python 实现的 Dijkstra 算法的长沙地铁线路查询系统的示例代码。该代码使用了邻接列表来存储每个站点的邻居和距离,使用了 heapq 模块实现了优先队列。
```python
import heapq
# 定义邻接列表
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')
# 示例:从岳麓区政府到梅溪湖的最短路径
path, distance = dijkstra(subway, '岳麓区政府', '梅溪湖')
print(path) # ['岳麓区政府', '岳麓大道', '望月湖', '湖南大学', '枫林路', '银盆岭', '梅溪湖']
print(distance) # 6.0
```
以上代码中,我们将长沙地铁线路建立为邻接列表 `subway`,其中每个站点对应一个字典,字典的键是邻居站点名,值是到邻居站点的距离。然后,我们实现了 `dijkstra` 函数来计算最短路径,该函数的输入参数为邻接列表、起点和终点,输出结果为最短路径和距离。在该函数中,我们使用了一个 `distances` 字典来记录每个站点到起点的距离,使用一个 `parents` 字典来记录每个站点的父节点,使用一个优先队列 `queue` 来存储当前距离最短的站点。在每次循环中,我们从优先队列中取出当前距离最短的站点,然后遍历其邻居,更新邻居的距离和父节点。如果当前站点已经是终点,则返回最短路径。如果无法到达终点,则返回空路径和无穷大的距离。