最短路径和时间最短代码
时间: 2024-02-05 15:10:42 浏览: 31
以下是Dijkstra算法的Python实现,用于求解带权重图中的最短路径和时间最短问题:
```
import heapq
def dijkstra(graph, start):
# 初始化距离字典和堆
distances = {node: float('inf') 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
heapq.heappush(heap, (distance, neighbor))
return distances
# 示例用法
graph = {
'A': {'B': 1, 'C': 4},
'B': {'C': 2, 'D': 5},
'C': {'D': 1},
'D': {}
}
shortest_distances = dijkstra(graph, 'A')
print(shortest_distances)
```
在上面的示例中,我们定义了一个有向带权重图,并使用Dijkstra算法求解了从节点'A'到其他节点的最短距离。输出结果为:
```
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
```
这表示从节点'A'到其他节点的最短距离分别为0、1、3和4。如果我们需要求解时间最短问题,则只需要将图中的权重定义为时间而非距离即可。