# Programme transcrit depuis la vidéo dont le lien est le suivant:
# https://www.youtube.com/watch?v=CWVk0hIJH4U&list=PL5ni4iEf8Z6Wqz2XJLMwUUJ18dQp2khSg&index=4

""" Graphe implémenté avec un dictionnaire """

def dijkstra(G,s):
    infini = sum(sum(G[sommet][i] for i in G[sommet]) for sommet in G) + 1

    s_connu = {s : [ 0, [s] ] } # [longueur, plus court chemin]
    s_inconnu = {k : [infini, ''] for k in G if k != s } # [longueur, précédent]
    for next in G[s]:
        s_inconnu[next] = [ G[s][next], s ]

    print("Plus 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 G[u]:
            if 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(s_connu[u][1]))

    return s_connu

G = {
    'K' : {
        'M' : 4,
        'E' : 1
    },
    'M' : {
        'E' : 2,
        'H' : 2
    },
    'E' : {
        'M' : 1,
        'H' : 3,
        'F' : 1
    },
    'H' : {
        'F' : 3
    },
    'F' : {
        'H' : 1
    },
    'S' : {
        'H' : 1,
        'F' : 2
    }
}

dijkstra(G,'K')

""" Graphe implémenté par matrice de valuation """

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

    s_connu = { s : [ 0, [s] ] } # [longueur, plus court chemin]
    s_inconnu = { k : [infini, ''] for k in range(nb_sommets) if k != s } # longueur, précédent

    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,4,1,0,3,0],
    [4,0,10,1,0,0],
    [1,10,0,5,1,0],
    [0,1,5,0,3,1],
    [3,0,1,3,0,1],
    [0,0,0,1,1,0]
]

print('\nAvec la matrice:')
dijkstraM(G,0)