关于#算法#的问题：使用 Dijkstra 算法找到最短路径

Question

请问 ，什么是最短路径问题？使用 Dijkstra 算法找到最短路径？

Answer 1

直接使用python的 Dijkstra 算法找到最短路径的例子

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        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(priority_queue, (distance, neighbor))
    return distances

# 示例用法
graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'C': 1, 'D': 3},
    'C': {'D': 1},
    'D': {}
}
start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(f"从节点 {start_node} 出发的最短距离为：{shortest_distances}")