# tp_labyrinthe.py

# Graphe orienté
labyrinthe = {
    1: [2],
    2: [3, 6],
    3: [4],
    4: [7],
    5: [3],
    6: [9],
    7: [8],
    8: [9],
    9: []
}

def ajoute_sommet(dico, chemin):
    dernier = chemin[-1]
    if dernier not in dico or not dico[dernier]:
        return []
    return [chemin + [successeur] for successeur in dico[dernier]]

def sortie(dico, i=1, j=9):
    chemins = [[i]]
    while chemins:
        chemin = chemins.pop()
        dernier = chemin[-1]
        if dernier == j:
            return chemin
        successeurs = dico.get(dernier, [])
        for successeur in successeurs:
            if successeur not in chemin:
                chemins.append(chemin + [successeur])
    return None

# Graphe non orienté
labyrinthe_non_oriente = {
    1: [2],
    2: [1, 3, 6],
    3: [2, 4, 5],
    4: [3, 7],
    5: [3],
    6: [2, 9],
    7: [4, 8],
    8: [7, 9],
    9: [6, 8]
}

def ajoute_sommet_non_oriente(dico, chemin):
    dernier = chemin[-1]
    successeurs = dico.get(dernier, [])
    return [chemin + [successeur] for successeur in successeurs if successeur not in chemin]

def sortie_non_oriente(dico, i=1, j=9):
    chemins = [[i]]
    while chemins:
        chemin = chemins.pop()
        dernier = chemin[-1]
        if dernier == j:
            return chemin
        for successeur in dico.get(dernier, []):
            if successeur not in chemin:
                chemins.append(chemin + [successeur])
    return None

# Graphe pondéré
dico_pond = {
    0: {2: 232, 4: 198, 6: 513},
    1: {4: 253, 5: 168},
    2: {0: 232, 3: 112, 7: 318},
    3: {2: 112, 5: 217},
    4: {0: 198, 1: 253, 5: 296},
    5: {1: 168, 3: 217, 4: 296, 7: 136},
    6: {0: 513, 7: 274},
    7: {2: 318, 5: 136, 6: 274}
}

def distance(dico, chemin):
    dist = 0
    for i in range(len(chemin) - 1):
        a, b = chemin[i], chemin[i + 1]
        dist += dico[a][b]
    return dist

def chemins_possibles(i, j, dico):
    chemins = [[i]]
    resultats = []
    while chemins:
        chemin = chemins.pop()
        dernier = chemin[-1]
        if dernier == j:
            resultats.append(chemin)
        else:
            for successeur in dico.get(dernier, {}):
                if successeur not in chemin:
                    chemins.append(chemin + [successeur])
    return resultats

def plus_court_chemin(dico, i, j):
    tous_les_chemins = chemins_possibles(i, j, dico)
    return min(tous_les_chemins, key=lambda c: distance(dico, c))

# Tests
if __name__ == "__main__":
    print("Tests labyrinthe orienté:")
    print(ajoute_sommet(labyrinthe, [1, 2]))      # [[1, 2, 3], [1, 2, 6]]
    print(sortie(labyrinthe))                      # [1, 2, 6, 9]
    print(sortie(labyrinthe, 5, 9))                # None

    print("\nTests labyrinthe non orienté:")
    print(ajoute_sommet_non_oriente(labyrinthe_non_oriente, [1, 2]))  # [[1, 2, 3], [1, 2, 6]]
    print(sortie_non_oriente(labyrinthe_non_oriente, 5, 9))           # [5, 3, 2, 6, 9]

    print("\nTests graphe pondéré:")
    print(distance(dico_pond, [0, 4, 1, 5]))       # 198 + 253 + 168 = 619
    print(chemins_possibles(0, 5, dico_pond))      # Plusieurs chemins possibles
    print(plus_court_chemin(dico_pond, 0, 5))      # Plus court chemin