给出一个规划单向最短路径的python算法
时间: 2023-12-01 14:55:16 浏览: 26
以下是使用Dijkstra算法实现单向最短路径规划的Python代码示例:
```python
import heapq
def dijkstra(graph, start, end):
# 初始化距离和前驱节点字典
distances = {node: float('inf') for node in graph}
prev_nodes = {node: None for node in graph}
distances[start] = 0
# 初始化最小堆,将起始节点入堆
heap = [(0, start)]
while heap:
# 取出当前最短距离的节点
current_distance, current_node = heapq.heappop(heap)
# 如果当前节点已经被访问过,跳过
if current_distance > distances[current_node]:
continue
# 遍历当前节点的邻居节点,更新距离和前驱节点
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
prev_nodes[neighbor] = current_node
heapq.heappush(heap, (distance, neighbor))
# 构建最短路径
path = []
node = end
while node is not None:
path.append(node)
node = prev_nodes[node]
path.reverse()
return path, distances[end]
```
其中,graph表示有向图,使用字典表示,如下所示:
```python
graph = {
'A': {'B': 2, 'C': 4},
'B': {'C': 1, 'D': 3},
'C': {'D': 1},
'D': {'A': 5}
}
```
start表示起始节点,end表示目标节点。调用dijkstra函数即可得到从起始节点到目标节点的最短路径和距离。