import matplotlib.pyplot as plt

g = {
    1: [(7,2),(6,5)],
    2: [(6,1),(1,1)],
    3: [(5,2),(8,6)],
    4: [((2,3))],
    5: [(4,1),(7,2),(8,3)],
    6: [(3,4), (4,1), (2,1)],
    7: [(5,3),(6,2)],
    8: [(4,6),(6,3)],
}

def degres(g):
    """
    Entrée: g un graphe représenté par listes d'adjacence
    Sortie: dictionnaire des degrés de g
    """
    degs = {}
    for u in g:
        degs[u] = len(g[u])
    return degs
    # version alternative
    # return {u: len(g[u]) for u in g}

def longueur(g, l):
    """
    Entrées: g graphe, l liste de sommets de g
    Sortie: longueur du chemin formé par l dans g
    Précondition: l doit représenter un chemin valide
    """
    res = 0
    for i in range(len(l)-1):
        u = l[i]
        v = l[i+1]
        # chercher v dans les voisins de u
        for vv, poids in g[u]:
            # poids est le poids de l'arete (u, v)
            if vv == v:
                res += poids
    return res



def extraire_min(Q, d):
    """
    Entrées:
    - Q ensemble
    - d dictionnaire dont les éléments de Q sont des clés
    Sortie: Renvoie un élément de Q u tel que d[u] est minimal,
            et supprime u de Q
    """
    best_u = None # meilleur élément vu jusqu'à maintenant
    best_score = float("inf") # meilleur score vu jusqu'à maintenant
    for u in Q:
        if d[u] < best_score:
            best_u = u
            best_score = d[u]
    Q.remove(best_u)
    return best_u


def dijkstra(G, s):
    """
    Entrées: G graphe, s sommet de G
    Sortie: couple (d, pred) avec d dictionnaire associant
    à chaque sommet u la distance de s à u et pred dictionnaire
    de l'arborescence, i.e. indiquant pour chaque sommet u son
    prédécesseur sur un plus court chemin depuis s
    """
    Q = set()
    d = {}
    for u in G:
        Q.add(u)
        d[u] = float("inf")

    d[s] = 0
    pred = {}
    while len(Q) > 0:
        u = extraire_min(Q, d)
        for v, t in G[u]:
            # v: voisin
            # t: longueur de l'arete (u, v)
            if d[u] + t < d[v]:
                d[v] = d[u] + t
                pred[v] = u
    return d, pred

def pcc(g, s, t):
    """
    Entrées: g un graphe, s et t deux sommets de g
    Sortie: plus court chemin de s à t, sous la forme
    d'une liste de sommets. Affiche la longueur de ce
    chemin. Renvoie None si t n'est pas atteignable
    depuis s.
    """
    d, p = dijkstra(g, s)
    if t not in p:
        # le sommet cible n'est pas atteignable
        return None

    # reconstruire le chemin à l'envers
    u = t
    res = [t]
    total = 0
    while u != s:
        u = p[u]
        res.append(u)

    # renvoyer la liste renversée
    k = len(res)
    return [res[k-i-1] for i in range(k)]

def test():
    ch = pcc(g, 2, 8)
    print(f"Plus court chemin de 2 à 8: {ch}")