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)