迪杰斯特拉算法最短路径

迪杰斯特拉算法是一种用于计算图中单源最短路径的贪心算法。它的主要思想是从起点开始，逐步扩展到其他节点，直到到达终点或者所有节点都被扩展。在扩展的过程中，维护一个距离数组，记录起点到每个节点的最短距离，同时维护一个集合，记录已经找到最短路径的节点。每次从未找到最短路径的节点中选择距离起点最近的节点进行扩展，更新距离数组中的距离值。重复这个过程，直到到达终点或者所有节点都被扩展。

以下是一个使用迪杰斯特拉算法求解最短路径的Python代码示例：

import heapq

def dijkstra(graph, start, end):
    # 初始化距离数组和已找到最短路径的节点集合
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    visited = set()

    # 使用堆优化的Dijkstra算法
    heap = [(0, start)]
    while heap:
        (d, node) = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        if node == end:
            return d
        for neighbor, cost in graph[node].items():
            if neighbor in visited:
                continue
            new_dist = dist[node] + cost
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    # 如果无法到达终点，返回None
    return None

# 示例图
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

# 求解A到F的最短路径
print(dijkstra(graph, 'A', 'F')) # 输出：8