import sys


def Dijkstra(graph, src):
    """
    :param graph: 邻接矩阵存储图
    :param src: 源点
    :return:
    """
    """
    path: 前驱节点
    dist: 最短路径长度
    final: 结点是否被访问标记[-1未被访问，0被访问]
    """

    """初始化path"""
    n = len(graph)
    path = [-1] * n
    dist = [sys.maxsize] * n
    dist[src] = 0
    final = [-1] * n
    final[src] = 0

    """初始化graph"""
    for i in range(len(graph)):
        for j in range(len(graph)):
            if graph[i][j] == 0:
                graph[i][j] = sys.maxsize
                
    """初始化dist"""
    for k in range(len(dist)):
        if graph[src][k] < dist[k]:
            dist[k] = graph[src][k]
            path[k] = src

    """寻找src最短距离"""
    for i in range(n):
        """每次最小值与下标"""
        min_dist = sys.maxsize
        min_dist_node = -1

        for j in range(len(dist)):
            if final[j] != 0 and dist[j] < min_dist:
                min_dist = dist[j]
                min_dist_node = j

        if min_dist_node != -1:
            num = min_dist_node
            """更新当前结点到各结点的距离,当前选择结点为num"""
            for u in range(len(graph[num])):
                if final[u] != 0 and graph[num][u] + dist[num] < dist[u]:
                    dist[u] = graph[num][u] + dist[num]
                    path[u] = num
            final[num] = 0
    return dist

if __name__ == '__main__':
    graph = [
        [0, 4, 0, 0, 0, 0, 0, 8, 0],
        [4, 0, 8, 0, 0, 0, 0, 11, 0],
        [0, 8, 0, 7, 0, 4, 0, 0, 2],
        [0, 0, 7, 0, 9, 14, 0, 0, 0],
        [0, 0, 0, 9, 0, 10, 0, 0, 0],
        [0, 0, 4, 14, 10, 0, 2, 0, 0],
        [0, 0, 0, 0, 0, 2, 0, 1, 6],
        [8, 11, 0, 0, 0, 0, 1, 0, 7],
        [0, 0, 2, 0, 0, 0, 6, 7, 0]
    ]
    print(Dijkstra(graph, 0))