import heapq
from math import inf

graphe_pondere = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("D", 1)],
    "C": [("A", 1), ("B", 2), ("D", 5)],
    "D": [("B", 1), ("C", 5)],
}

def dijkstra(graphe: dict, depart: str) -> dict[str, float]:
    # Complexité : O((V + E) log V) avec un tas binaire -- exige des poids POSITIFS
    distances = {sommet: inf for sommet in graphe}
    distances[depart] = 0
    file_priorite = [(0, depart)]   # (distance_actuelle, sommet)
    visites = set()

    while file_priorite:
        distance_actuelle, sommet = heapq.heappop(file_priorite)

        if sommet in visites:
            continue   # entrée obsolète (on a trouvé mieux depuis) -- on l'ignore simplement
        visites.add(sommet)

        for voisin, poids in graphe.get(sommet, []):
            nouvelle_distance = distance_actuelle + poids
            if nouvelle_distance < distances[voisin]:   # relâchement (relaxation) de l'arête
                distances[voisin] = nouvelle_distance
                heapq.heappush(file_priorite, (nouvelle_distance, voisin))

    return distances

resultat = dijkstra(graphe_pondere, "A")
assert resultat == {"A": 0, "B": 3, "C": 1, "D": 4}   # A->C->B->D = 1+2+1 = 4, meilleur que A->B direct

# --- Reconstruire le CHEMIN complet, pas seulement la distance ---
def dijkstra_avec_chemin(graphe: dict, depart: str, arrivee: str) -> tuple[float, list[str]]:
    distances = {sommet: inf for sommet in graphe}
    distances[depart] = 0
    predecesseurs: dict[str, str | None] = {depart: None}
    file_priorite = [(0, depart)]
    visites = set()

    while file_priorite:
        distance_actuelle, sommet = heapq.heappop(file_priorite)
        if sommet in visites:
            continue
        visites.add(sommet)
        if sommet == arrivee:
            break   # optimisation : on peut s'arrêter dès que la cible est finalisée

        for voisin, poids in graphe.get(sommet, []):
            nouvelle_distance = distance_actuelle + poids
            if nouvelle_distance < distances[voisin]:
                distances[voisin] = nouvelle_distance
                predecesseurs[voisin] = sommet
                heapq.heappush(file_priorite, (nouvelle_distance, voisin))

    if distances[arrivee] == inf:
        return inf, []

    chemin = [arrivee]
    while predecesseurs[chemin[-1]] is not None:
        chemin.append(predecesseurs[chemin[-1]])
    return distances[arrivee], chemin[::-1]

distance, chemin = dijkstra_avec_chemin(graphe_pondere, "A", "D")
assert distance == 4
assert chemin == ["A", "C", "B", "D"]

# --- Pourquoi Dijkstra échoue avec des poids négatifs ---
# Dijkstra suppose qu'une fois un sommet "visité" (finalisé), sa distance ne peut plus diminuer.
# Un poids négatif peut invalider cette hypothèse APRÈS la finalisation -- résultat incorrect silencieux.
# Solution avec poids négatifs (sans cycle négatif) : Bellman-Ford, O(V * E)
def bellman_ford(graphe_aretes: list[tuple[str, str, float]], sommets: list[str], depart: str) -> dict[str, float]:
    distances = {sommet: inf for sommet in sommets}
    distances[depart] = 0

    for _ in range(len(sommets) - 1):   # V-1 itérations garantissent la convergence
        for a, b, poids in graphe_aretes:
            if distances[a] != inf and distances[a] + poids < distances[b]:
                distances[b] = distances[a] + poids

    # Vème itération : si une distance diminue encore, il y a un cycle de poids négatif
    for a, b, poids in graphe_aretes:
        if distances[a] != inf and distances[a] + poids < distances[b]:
            raise ValueError("Cycle de poids négatif détecté")

    return distances

aretes = [("A", "B", 4), ("A", "C", 1), ("C", "B", 2), ("B", "D", 1), ("C", "D", 5)]
assert bellman_ford(aretes, ["A", "B", "C", "D"], "A") == {"A": 0, "B": 3, "C": 1, "D": 4}