线路规划代码
时间: 2023-07-02 09:10:58 浏览: 69
以下是一个简单的线路规划代码,使用了 Dijkstra 算法来计算最短路程:
```python
import heapq
def dijkstra(graph, start, end):
# 初始化距离和父节点字典
distances = {vertex: float('inf') for vertex in graph}
parents = {vertex: None for vertex in graph}
distances[start] = 0
visited = []
# 使用堆来进行优先级队列操作
pq = [(0, start)]
while pq:
(current_distance, current_vertex) = heapq.heappop(pq)
visited.append(current_vertex)
# 如果到达终点,则返回路径
if current_vertex == end:
path = []
while current_vertex is not None:
path.append(current_vertex)
current_vertex = parents[current_vertex]
path.reverse()
return path
# 遍历邻接节点
for neighbor, weight in graph[current_vertex].items():
if neighbor in visited:
continue
new_distance = current_distance + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
parents[neighbor] = current_vertex
heapq.heappush(pq, (new_distance, neighbor))
# 如果无法到达终点,则返回空列表
return []
# 示例图
graph = {
'A': {'B': 5, 'C': 1},
'B': {'A': 5, 'C': 2, 'D': 1},
'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
'E': {'C': 8, 'D': 3},
'F': {'D': 6}
}
# 计算从 A 到 F 的最短路径
start = 'A'
end = 'F'
path = dijkstra(graph, start, end)
print(f'Shortest path from {start} to {end}: {path}')
```
输出:
```
Shortest path from A to F: ['A', 'C', 'D', 'F']
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)