import networkx as nx
import matplotlib.pyplot as plt

def construit_graphe_pondere():
    G = nx.Graph()
    G.add_nodes_from(['A', 'B', 'C', 'D', 'E']) # on ajoute les sommets
    aretes = [
        ('A', 'B', 2),
        ('A', 'D', 5),
        ('B', 'C', 1),
        ('B', 'D', 2),
        ('B', 'E', 3),
        ('C', 'E', 2),
        ('D', 'E', 4)
    ]
    for u, v, poids in aretes:
        G.add_edge(u, v, weight=poids) # on ajoute les aretes
    return G

def dijkstra_A_E(G):
    chemin = nx.dijkstra_path(G, source='A', target='E')
    longueur = nx.dijkstra_path_length(G, source='A', target='E')
    
    print(f"Plus court chemin A → E : {' → '.join(chemin)}")
    print(f"Longueur du chemin : {longueur}")
    
    return chemin, longueur

def affiche_graphe_chemin(G, chemin):
    pos = {
        'A': (0, 0),
        'B': (2, 1.5),
        'C': (4, 0),
        'D': (0, -2),
        'E': (4, -2)
    }
    # Toutes les arêtes en noir
    nx.draw_networkx_nodes(G, pos, node_color='lightblue', node_size=800)
    nx.draw_networkx_edges(G, pos, width=2, alpha=0.7)
    
    # Arêtes du chemin en rouge épais
    aretes_chemin = list(zip(chemin, chemin[1:]))
    nx.draw_networkx_edges(G, pos, edgelist=aretes_chemin, 
                          edge_color='red', width=4, alpha=0.9)
    
    nx.draw_networkx_labels(G, pos, font_size=16, font_weight='bold')
    
    # Labels poids seulement sur arêtes du chemin (optionnel, plus clair)
    edge_labels = {edge: G[edge[0]][edge[1]]['weight'] for edge in aretes_chemin}
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=12)
    
    plt.title("Plus court chemin A → E (rouge)")
    plt.axis('off')
    plt.tight_layout()
    plt.show()

G = construit_graphe_pondere()
print(f"Graphe créé : {G.nodes()} | {G.edges(data=True)}\n")
    
# Question 3
print("\n(3) Calcul Dijkstra A → E")
chemin, longueur = dijkstra_A_E(G)
    
# Question 4
print("\n(4) Affichage avec chemin mis en évidence")
affiche_graphe_chemin(G, chemin)