图的最短路径问题（迪杰斯特拉算法）

迪杰斯特拉算法是一种用于解决带权有向图或无向图的单源最短路径的贪心算法。该算法的基本思想是：对于图中的一个源点，维护一个到该源点的距离数组，初始时，源点到自身的距离为0，其余点到源点的距离为无穷大。然后，每次从距离数组中选择一个距离最小的点，将该点加入到已确定最短路径的集合中，并更新该点的邻居节点的距离数组。重复该过程，直到所有节点都被加入到已确定最短路径的集合中。

下面是一个使用Python实现迪杰斯特拉算法的例子：

import sys

def dijkstra(graph, start):
    # 初始化距离数组
    dist = {node: sys.maxsize for node in graph}
    dist[start] = 0

    # 初始化已确定最短路径的集合
    visited = set()

    while len(visited) < len(graph):
        # 选择距离最小的点
        node = min(set(dist.keys()) - visited, key=dist.get)

        # 更新该点的邻居节点的距离数组
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist

        # 将该点加入到已确定最短路径的集合中
        visited.add(node)

    return dist

# 测试
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}
}

start = 'A'
dist = dijkstra(graph, start)
print(dist)

上述代码中，我们使用了一个邻接表来表示图，其中每个节点都是一个字典，字典的键表示该节点的邻居节点，值表示该节点到邻居节点的边权重。在dijkstra函数中，我们首先初始化距离数组和已确定最短路径的集合，然后重复选择距离最小的点，并更新该点的邻居节点的距离数组，直到所有节点都被加入到已确定最短路径的集合中。最后，我们返回距离数组，即每个节点到起点的最短距离。