Dijkstra算法是一种用于计算单源最短路径的经典算法,它并不一定是对称的。
Dijkstra算法通过逐步扩展已知最短路径的集合来工作,直到找到从源节点到所有其他节点的最短路径。它使用了一个优先队列(通常是基于最小堆实现)来选择下一个要处理的节点。
以下是一个使用Python实现的Dijkstra算法示例:
import heapq
def dijkstra(graph, start):
queue = []
heapq.heappush(queue, (0, start))
distances = {node: float('inf') for node in graph}
distances[start] = 0
shortest_path = {}
while queue:
(dist, current) = heapq.heappop(queue)
if dist > distances[current]:
continue
for neighbor, weight in graph[current].items():
distance = dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
shortest_path[neighbor] = current
return distances, shortest_path
# 示例图
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
distances, shortest_path = dijkstra(graph, 'A')
print("Distances:", distances)
print("Shortest Path:", shortest_path)
领取专属 10元无门槛券
手把手带您无忧上云