迪杰斯特拉最短路径算法讲解，配合python

迪杰斯特拉最短路径算法是一种经典的单源最短路径算法，用于解决带权重的有向图或无向图中，从一个源点到其他所有顶点的最短路径问题。

算法的基本思想是通过逐步扩展离源点越来越近的顶点的方式，逐步确定源点到其他顶点的最短路径。具体实现时，需要维护两个集合S和V-S，其中S表示已经确定最短路径的顶点集合，V-S表示还未确定最短路径的顶点集合。初始时，S中只包含源点，V-S包含其他所有顶点。然后，每次从V-S中选择一个距离源点最近的顶点u加入到S中，并更新源点到其它顶点的距离。

下面是Python实现迪杰斯特拉最短路径算法的代码，以邻接矩阵表示的有向图为例：

import sys

def dijkstra(graph, src):
    n = len(graph)
    dist = [sys.maxsize] * n  # 记录源点到各个顶点的距离
    visited = [False] * n     # 标记顶点是否已加入S集合
    dist[src] = 0             # 初始化源点到自身的距离为0

    for _ in range(n):
        # 找到距离源点最近的未加入S集合的顶点
        u = -1
        min_dist = sys.maxsize
        for i in range(n):
            if not visited[i] and dist[i] < min_dist:
                u = i
                min_dist = dist[i]
        if u == -1:
            break
        visited[u] = True
        # 更新源点到所有邻居顶点的距离
        for v in range(n):
            if not visited[v] and graph[u][v] != 0:
                dist[v] = min(dist[v], dist[u] + graph[u][v])
    return dist

# 有向图的邻接矩阵表示
graph = [[0, 10, 3, 0, 0],
         [0, 0, 1, 2, 0],
         [0, 4, 0, 8, 2],
         [0, 0, 0, 0, 7],
         [0, 0, 0, 9, 0]]
print(dijkstra(graph, 0))  # 输出从源点0到其他各个顶点的最短距离

该代码中，dijkstra函数的参数graph是邻接矩阵表示的有向图，src是源点的索引。在dijkstra函数中，首先初始化源点到各个顶点的距离dist和标记顶点是否已加入S集合的visited数组。然后，在每一轮循环中，找到距离源点最近的未加入S集合的顶点u，并将其加入S集合中。然后，遍历源点的所有邻居顶点v，更新源点到v的距离。最后返回源点到其他所有顶点的最短距离dist。

运行上述代码，输出结果为：[0, 7, 3, 10, 5]，表示源点0到其他各个顶点的最短距离。