import math


def dijkstra(g):
    unvisited = list(range(9))
    distances = [0] + [math.inf] * 8

    while unvisited:
        # pop out the one with minimal distance
        cur_node_idx = unvisited[0]
        if cur_node_idx == 8:
            break
        cur_node = g[cur_node_idx]
        next_nodes = [
            (idx, d) for (idx, d) in enumerate(cur_node) if idx in unvisited and d != 0
        ]
        for idx, d in next_nodes:
            distances[idx] = min(distances[cur_node_idx] + d, distances[idx])

        unvisited.remove(cur_node_idx)
        unvisited = sorted(unvisited, key=lambda idx: distances[idx])

    print(distances)


g = [
    [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],
]

dijkstra(g)


import math


def dijkstra(g):
    unvisited = list(range(9))
    distances = [0] + [math.inf] * 8

    while unvisited:
        # pop out the one with minimal distance
        cur_node_idx = unvisited[0]
        if cur_node_idx == 8:
            break
        cur_node = g[cur_node_idx]
        next_nodes = [
            (idx, d) for (idx, d) in enumerate(cur_node) if idx in unvisited and d != 0
        ]
        for idx, d in next_nodes:
            distances[idx] = min(distances[cur_node_idx] + d, distances[idx])

        unvisited.remove(cur_node_idx)
        unvisited = sorted(unvisited, key=lambda idx: distances[idx])

    print(distances)


g = [
    [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],
]

dijkstra(g)


# pop out the one with minimal distance