Dijkstra方法的代码实现python数据结构

以下是 Dijkstra 算法的 Python 代码实现，使用了 heapq （堆）和 defaultdict （默认字典）两种数据结构：

import heapq
from collections import defaultdict

def dijkstra(edges, start, end):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((w, v))

    heap = [(0, start)]
    visited = set()
    while heap:
        (curr_cost, curr_node) = heapq.heappop(heap)
        if curr_node in visited:
            continue
        visited.add(curr_node)
        if curr_node == end:
            return curr_cost
        for cost, neighbor in graph[curr_node]:
            if neighbor not in visited:
                heapq.heappush(heap, (curr_cost + cost, neighbor))

    return -1  # 无法到达

# 示例用法
edges = [
    ('A', 'B', 3),
    ('A', 'D', 2),
    ('D', 'B', 1),
    ('D', 'C', 5),
    ('B', 'C', 2),
    ('B', 'E', 1),
    ('C', 'E', 4),
    ('C', 'F', 4),
    ('E', 'F', 1)
]
start = 'A'
end = 'F'
print(dijkstra(edges, start, end))  # 输出 7

其中，`edges` 是一个包含边信息的列表，每个元素是一个三元组 `(u, v, w)`，表示从节点 `u` 到节点 `v` 的边权重为 `w`。`start` 和 `end` 分别表示起点和终点节点。函数返回从起点到终点的最短路径长度，如果无法到达终点，则返回 -1。