迪杰斯特拉最短路径算法【图】

迪杰斯特拉最短路径算法是一种解决有权图中单源最短路径问题的算法。它采用贪心策略，以起始点为中心向外层层扩展，直到扩展到终点为止。该算法主要特点是将图中的节点集分为最短路径计算完成的节点集S和未计算完成的节点集T，每次将从T中挑选V0->Vt最小的节点Vt加入S，并更新V0经由Vt到T中剩余节点的更短距离，直到T中的节点全部加入S中。迪杰斯特拉算法只支持非负权图，它计算的是单源最短路径，即单个源点到剩余节点的最短路径，时间复杂度为O(n²)。

以下是迪杰斯特拉最短路径算法的具体步骤：
1. 初始化：将起始点s加入S集合，将与s直接相连的节点的距离加入dis数组，将其余节点的距离设为无穷大。
2. 重复执行以下步骤，直到T集合为空：
a. 从dis数组中选择值最小的节点v，将其加入S集合。
b. 更新dis数组：对于T集合中的每个节点w，如果存在一条从v到w的边，则计算出v到w的距离，并将其与原有距离进行比较，如果更小则更新dis数组中w的值。
3. 得到起始点s到各个节点的最短路径。

以下是Python实现迪杰斯特拉最短路径算法的代码示例：

import sys

def dijkstra(graph, start):
    # 初始化
    dis = {node: sys.maxsize for node in graph} # 距离数组
    dis[start] = 0
    S = set() # 最短路径节点集合
    T = set(graph.keys()) # 未计算最短路径节点集合

    while T:
        # 选择距离起点最近的节点
        v = min(T, key=lambda node: dis[node])
        S.add(v)
        T.remove(v)

        # 更新距离数组
        for w in graph[v]:
            if dis[w] > dis[v] + graph[v][w]:
                dis[w] = dis[v] + graph[v][w]

    return dis

# 测试
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'
print(dijkstra(graph, start)) # 输出：{'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7, 'F': 10}