#Graphes avancésCopier le lien

Prérequis : chapitres Parcours de graphes et Dijkstra ; structure union-find utile mais reconstruite ici.

Objectifs d'apprentissage : implémenter Bellman-Ford avec détection de cycle négatif ; construire un arbre couvrant minimal par Kruskal (tri + union-find) et par Prim (tas) ; comprendre Floyd-Warshall par ses trois boucles ; savoir quel algorithme appeler selon le contexte.

#1. Choisir son algorithmeCopier le lien

#2. Dijkstra : rappel opérationnelCopier le lien

L'algorithme de Dijkstra résout la source unique quand tous les poids sont non négatifs. Sa preuve et son implémentation détaillées sont au chapitre Dijkstra ; le chapitre gloutons en donne la lecture « pari local » :

1import heapq2 3def dijkstra(graphe, source):4    distances = {s: float('inf') for s in graphe}5    distances[source] = 06    file = [(0, source)]7    while file:8        d, u = heapq.heappop(file)9        if d > distances[u]:10            continue                        # entrée périmée11        for v, poids in graphe[u].items():12            if d + poids < distances[v]:13                distances[v] = d + poids14                heapq.heappush(file, (distances[v], v))

#VisualisationCopier le lien

Entrées : graphe pondéré non négatif et source. Sorties : ordre de figement et distances finales. Comparez avec Bellman-Ford ci-dessous : le même graphe traverse plus d'itérations, mais la méthode survit aux poids négatifs.

#3. Bellman-Ford : survivre aux poids négatifsCopier le lien

L'idée : relâcher toutes les arêtes, V-1 fois de suite. Après la i-ème passe, distances[v] est au plus la longueur du plus court chemin utilisant au plus i arêtes ; un plus court chemin simple compte au plus V-1 arêtes, d'où le compte de passes.

1def bellman_ford(graphe, source):2    """Distances minimales avec poids négatifs autorisés.3    Lève ValueError si un cycle de poids négatif est atteignable."""4    distances = {s: float('inf') for s in graphe}5    distances[source] = 06 7    for _ in range(len(graphe) - 1):8        for u in graphe:9            for v, poids in graphe[u].items():10                if distances[u] + poids < distances[v]:11                    distances[v] = distances[u] + poids12 13    # Passe supplémentaire : si une distance bouge encore,14    # un cycle négatif est atteignable depuis la source.

La passe de détection n'est pas un gadget : avec un cycle négatif, la notion de plus court chemin perd son sens (on peut boucler en diminuant sans fin le coût). Le prix à payer : O(V · E), contre O((V + E) log V) pour Dijkstra ; sur un graphe dense aux poids tous positifs, ne payez pas pour ce que vous n'utilisez pas.

#4. Arbres couvrants minimauxCopier le lien

Problème : connecter tous les sommets d'un graphe non orienté pondéré en minimisant la somme des poids des arêtes retenues. Deux stratégies gloutonnes optimales, prouvées par échange sur la coupe.

#Kruskal : trier les arêtes, éviter les cyclesCopier le lien

On trie toutes les arêtes par poids croissant et on retient chacune si elle relie deux composantes différentes. La structure union-find répond à « ces deux sommets sont-ils déjà reliés ? » en temps quasi constant (compression de chemin + union par rang).

1class UnionFind:2    def __init__(self, taille):3        self.parent = list(range(taille))4        self.rang = [0] * taille5 6    def find(self, x):7        if self.parent[x] != x:8            self.parent[x] = self.find(self.parent[x])   # compression de chemin9        return self.parent[x]10 11    def union(self, x, y):12        rx, ry = self.find(x), self.find(y)13        if rx == ry:14            return False          # déjà reliés : l'arête créerait un cycle

#Prim : faire grandir une seule composanteCopier le lien

Depuis un sommet de départ, on ajoute à chaque étape l'arête de poids minimale qui relie l'arbre en construction à un sommet extérieur. Un tas d'arêtes candidates donne O(E log V).

1import heapq2 3def prim(graphe, depart):4    """graphe non orienté : dict sommet -> dict voisin -> poids."""5    arbre = []6    dans_arbre = {depart}7    tas = [(poids, depart, voisin) for voisin, poids in graphe[depart].items()]8    heapq.heapify(tas)9    while tas:10        poids, u, v = heapq.heappop(tas)11        if v in dans_arbre:12            continue13        dans_arbre.add(v)14        arbre.append((u, v, poids))

Quand choisir quoi : Kruskal brille sur les graphes clairsemés (le tri domine) et quand les arêtes sont déjà disponibles en liste ; Prim sur les graphes denses où l'on grandit localement. Les deux renvoient un arbre de même poids total (l'ACM est unique ici car tous les poids sont distincts ; en cas d'égalités, plusieurs arbres optimaux existent).

#5. Floyd-Warshall : toutes les paires en trois bouclesCopier le lien

La programmation dynamique prend le relais : dist[k][i][j] est le plus court chemin de i à j dont les sommets intermédiaires sont parmi les k premiers. Soit le chemin optimal évite k (dist[k-1][i][j]), soit il passe par k (dist[k-1][i][k] + dist[k-1][k][j]).

1def floyd_warshall(matrice):2    """matrice[i][j] : poids de i à j, 0 sur la diagonale, inf si absente."""3    n = len(matrice)4    dist = [ligne[:] for ligne in matrice]5    for k in range(n):6        for i in range(n):7            for j in range(n):8                if dist[i][k] + dist[k][j] < dist[i][j]:9                    dist[i][j] = dist[i][k] + dist[k][j]10    return dist11 12INF = float('inf')13matrice = [14    [0, 3, INF, 7],

L'ordre des boucles importe : k (l'indice de l'intermédiaire autorisé) doit être la boucle externe. Complexité O(V³) en temps et O(V²) en mémoire, indépendamment du nombre d'arêtes : c'est le bon choix pour un graphe dense de taille modérée et des questions toutes-paires ; pour une source unique sur un grand graphe clairsemé, retournez à Dijkstra.

#6. Flots : aperçuCopier le lien

Les problèmes de transport se modélisent en réseau de capacité : une source, un puits, des arêtes bornées. Ford-Fulkerson répète la recherche d'un chemin augmentateur (dans le graphe résiduel, où les arêtes peuvent être parcourues en sens inverse pour « annuler » un flux) et pousse le maximum le long de ce chemin, jusqu'à n'en plus trouver. Avec un BFS pour choisir le chemin (Edmonds-Karp), la complexité devient O(V · E²). L'application type : couplage, découpe de projets, affectation de tâches. Ce panorama suffit au niveau L3 ; l'implémentation complète relève d'un cours dédié.

#7. Exercices avec vérificationCopier le lien

1. Floyd-Warshall guidé : implémentez l'algorithme à partir de la matrice ci-dessus. Vérification : la distance de 2 vers 1 vaut 3 (2 -> 3 -> 0 -> 1) et la diagonale reste nulle.
2. Kruskal sur papier puis en code : ajoutez l'arête (1, 2, 2) à la liste d'exemple et vérifiez que l'arbre retenu change et que son coût total vaut 11.
3. Union-find sous tension : mesurez le nombre total d'appels find avec et sans compression de chemin sur un graphe aléatoire de 1000 sommets ; l'écart illustre le gain quasi constant.