Graphes

#GraphesCopier le lien

Définitions, représentations, parcours (BFS/DFS) et applications classiques.

#Parcours BFS (liste d’adjacence)Copier le lien

#Exercice : Algorithme de Dijkstra pour les plus courts cheminsCopier le lien

Implémentez l'algorithme de Dijkstra pour trouver les plus courts chemins depuis un sommet source dans un graphe pondéré.

#InstructionsCopier le lien

1. Utilisez une file de priorité (min-heap) pour stocker les sommets à visiter.
2. Initialisez les distances à l'infini, sauf pour le sommet source (distance 0).
3. Pour chaque sommet, mettez à jour les distances de ses voisins si un chemin plus court est trouvé.
4. Marquez les sommets comme visités pour éviter les traitements multiples.

#Exemple de codeCopier le lien

1import heapq2from collections import defaultdict3 4def dijkstra(graph, start):5    # Initialisation des distances6    distances = defaultdict(lambda: float('inf'))7    distances[start] = 08    9    # File de priorité: (distance, sommet)10    pq = [(0, start)]11    visited = set()12    13    while pq:14        current_distance, current_vertex = heapq.heappop(pq)