pyhon中Dijkstra算法的实现

算法一，Dijkstra算法

Dijskstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。

单源最短路

• 贪心算法：每次找最近的点，局部最优等于全局最优，数学归纳法可证
• 维护起点 start 到每个点的距离
• 时间复杂度 O(n^2)
• 附加空间复杂度 O(n)

算法实现：

_ = float('inf')


def dijkstra(graph, n):
    dis = [0] * n
    flag = [False] * n
    pre = [0] * n
    flag[0] = True
    k = 0
    for i in range(n):
        dis[i] = graph[k][i]

    for j in range(n - 1):
        mini = _
        for i in range(n):
            if dis[i] < mini and not flag[i]:
                mini = dis[i]
                k = i
        if k == 0:  # 不连通
            return
        flag[k] = True
        for i in range(n):
            if dis[i] > dis[k] + graph[k][i]:
                dis[i] = dis[k] + graph[k][i]
                pre[i] = k
            #       print(k)
    return dis, pre


if __name__ == '__main__':
    n = 6
    graph = [
        [0, 6, 3, _, _, _],
        [6, 0, 2, 5, _, _],
        [3, 2, 0, 3, 4, _],
        [_, 5, 3, 0, 2, 3],
        [_, _, 4, 2, 0, 5],
        [_, _, _, 3, 5, 0],
    ]
    dis, pre = dijkstra(graph, n)
    print(dis)
    print(pre)

得出此图的结果为