def dijkstraM(G,s):
    infini = sum(sum(ligne) for ligne in G) + 1
    nb_sommets = len(G)

    s_connu = { s : [ 0, [s] ] }
    s_inconnu = { k : [infini, ''] for k in range(nb_sommets) if k != s }

    for next in range(nb_sommets):
        if G[s][next]:
            s_inconnu[next] = [ G[s][next], s ]

    print("\nPlus courts chemins de...")

    while s_inconnu and any(s_inconnu[k][0] < infini for k in s_inconnu):
        u = min(s_inconnu, key = s_inconnu.get)
        longueur_u, precedent_u = s_inconnu[u]
        for v in range(nb_sommets):
            if G[u][v] and v in s_inconnu:
                d = longueur_u + G[u][v]
                if d < s_inconnu[v][0]:
                    s_inconnu[v] = [ d, u ]
        s_connu[u] = [ longueur_u, s_connu[precedent_u][1] + [u] ]
        del s_inconnu[u]
        print("Longueur",longueur_u,":", ' -> '.join(map(str, s_connu[u][1])))

    return s_connu

G = [
    [0, 8, 6, 28, 5, 0, 0, 0, 0 ],
    [8, 0, 9, 0, 15, 0, 0, 0, 0 ],
    [6, 9, 0, 13, 0, 0, 0, 38, 0 ],
    [28, 0, 13, 0, 14, 0, 21, 17, 0],
    [5, 15, 0, 14, 0, 10, 17, 0, 0],
    [0, 0, 0, 0, 10, 0, 19, 0, 0],
    [0, 0, 0, 21, 17, 19, 0, 5, 17],
    [0, 0, 38, 17, 0, 0,5, 0, 16],
    [0, 0, 0, 0, 0, 0, 17, 16, 0]
]

dijkstraM(G,0)