算法策略

Dijkstra 算法是求一个图中一个点到其他所有点的最短路径的算法，先了解图的数据结构「邻接矩阵」

Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法，时间复杂度 O(n2)

B站视频：https://www.bilibili.com/video/av38254646/?vd_source=3fa2d314205867b74c99b14fd102f85c

要点

每次从「未求出最短路径的点」中取出距离起点最小路径的点，以这个点为桥梁刷新「未求出最短路径的点」的距离。

示例

找到以A点为起点，到各个点的最短距离

设定初始值

算法步骤

def dijkstra(graph, start_index):
    length = len(graph)
    res = [[x, float('inf'), 1] for x in range(length)]  # [索引，初始值最短距离暂定为正无穷，是否封闭（1不封闭，-1为封闭）]
    res[start_index][1] = 0  # 起始点的初始值设定

    #启动dijkstra算法
    for i in range(length-1):  # 扣除最后一个点
        # 查找路径最小值
        min_index = -1  # 设定默认索引为-1
        min_distance = float('inf')  # 设定默认最短路径结点值为无穷大
        for j in range(length):
            if res[j][2] != -1:  # 如果没有封闭
                if min_distance > res[j][1]:
                    min_distance = res[j][1] # 选取最小的路径值的点的值
                    min_index = res[j][0]  # 选取最小的路径值的点的索引
        res[min_index][2] = -1  # 将最小的路径值的点封闭
        print(res[min_index])
        # 更新最短路径数据
        for j in range(length):  # 找到邻近的结点
            if graph[min_index][j] != -1 and res[j][2] != -1:  # 有交集（不为-1） and 未封闭点（不为-1）
                if min_distance + graph[min_index][j] < res[j][1]:  # 如果最小的路径值+路径值 比原有的小，即更新
                    res[j][1] = min_distance + graph[min_index][j]

    return [x[1] for x in res]
# Test case
# vertices = ['A', 'B', 'C', 'D','E']
graph = [
    [0, 6, -1, 1,-1],
    [6, 0, 5, 2, 2],
    [-1, 5, 0, -1,5],
    [1, 2, -1, 0, 1],
    [-1,2, 5, 1, 0]
]
graph = [
    [0,10,-1,4,-1,-1],
    [10, 0, 8, 2, 6,-1],
    [-1,8,0,15,1,5],
    [4,2,15,0,6,-1],
    [-1,6,1,6,0,12],
    [-1,-1,5,-1,12,0]
]
print(dijkstra(graph, 0))  # Output: [0, 3, 7, 1, 2]