地铁换乘最短路径课设代码
时间: 2024-06-24 15:00:42 浏览: 6
在地铁换乘最短路径的课设中,通常会使用图论算法,如Dijkstra算法或A*算法,来找到从一个站点到另一个站点的最短路径。这里是一个简单的Python代码示例,使用了Dijkstra算法:
```python
import heapq
# 定义节点和边的数据结构
class Node:
def __init__(self, name):
self.name = name
self.dist = float('inf')
self.prev = None
class Edge:
def __init__(self, start, end, cost):
self.start = start
self.end = end
self.cost = cost
# Dijkstra算法实现
def dijkstra(graph, start):
queue = [(0, start)]
graph[start].dist = 0
while queue:
curr_dist, curr_node = heapq.heappop(queue)
if curr_dist > graph[curr_node].dist: # 如果已经更短,跳过
continue
for edge in graph[curr_node].edges: # 遍历当前节点的邻接节点
new_dist = curr_dist + edge.cost
if new_dist < graph[edge.end].dist:
graph[edge.end].dist = new_dist
graph[edge.end].prev = curr_node
heapq.heappush(queue, (new_dist, edge.end))
# 示例用法
graph = {
'A': [Edge('A', 'B', 1), Edge('A', 'C', 3)],
'B': [Edge('B', 'D', 1)],
'C': [Edge('C', 'D', 2)],
'D': [],
}
dijkstra(graph, 'A') # 从'A'开始找最短路径
shortest_path = []
node = 'D'
while node is not None:
shortest_path.append(node)
node = graph[node].prev
shortest_path.reverse() # 反转路径,因为队列的出队顺序是从后往前
print("Shortest path from A to D:", shortest_path, "with total cost", graph['D'].dist)
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)