Algorithmes de graphes : parcours et plus courts chemins

Algorithmes de graphes : parcours et plus courts chemins

1. Représentation des graphes

Un graphe $G=(V,E)$ est constitué d'un ensemble de sommets $V$ (taille $n=|V|$) et d'arêtes $E$ (taille $m=|E|$), orientées ou non. Deux représentations usuelles : la matrice d'adjacence (tableau $n\times n$, accès $O(1)$ à une arête, mais $O(n^2)$ de mémoire — adaptée aux graphes denses) et la liste d'adjacence (pour chaque sommet, la liste de ses voisins, mémoire $O(n+m)$ — adaptée aux graphes creux, cas le plus fréquent en pratique).

2. Parcours en profondeur (DFS)

Le parcours en profondeur (Depth-First Search) explore un graphe en allant aussi loin que possible avant de revenir en arrière (backtracking), à l'aide d'une pile (explicite ou via la récursion). Complexité : $O(n+m)$ (chaque sommet et chaque arête est visité une fois).

DFS(G, s) :

marquer s comme visité

pour chaque voisin v de s non visité :

DFS(G, v)

Applications : détection de cycles, tri topologique d'un graphe orienté acyclique (DAG), recherche des composantes connexes.

3. Parcours en largeur (BFS)

Le parcours en largeur (Breadth-First Search) explore le graphe niveau par niveau à partir d'une source $s$, à l'aide d'une file. Complexité $O(n+m)$.

BFS(G, s) :

enfiler s, marquer s comme visité, distance(s)=0

tant que la file n'est pas vide :

u = défiler()

pour chaque voisin v de u non visité :

marquer v, distance(v) = distance(u)+1, enfiler v

Propriété clé : dans un graphe non pondéré, le BFS calcule exactement les plus courts chemins (en nombre d'arêtes) depuis $s$ vers tous les autres sommets atteignables.

4. Algorithme de Dijkstra (plus courts chemins, poids positifs)

Pour un graphe pondéré par des poids strictement positifs, l'algorithme de Dijkstra calcule les plus courts chemins depuis une source $s$ vers tous les autres sommets, en utilisant une file de priorité (tas-min) sur les distances provisoires :

Dijkstra(G, s) :

dist(s) = 0, dist(v) = +infini pour v ≠ s

file de priorité Q = {tous les sommets, priorité = dist}

tant que Q n'est pas vide :

u = extraire le sommet de Q de plus petite distance

pour chaque voisin v de u (arête de poids w) :

si dist(u) + w < dist(v) :

dist(v) = dist(u) + w (relaxation)

mettre à jour la priorité de v dans Q

Complexité : $O((n+m)\log n)$ avec une implémentation par tas binaire (chaque extraction et chaque mise à jour de priorité coûte $O(\log n)$, et il y a $O(m)$ relaxations au total).

Exemple résolu. Graphe orienté : $A\to B$ (poids $4$), $A\to C$ (poids $1$), $C\to B$ (poids $2$), $B\to D$ (poids $1$), $C\to D$ (poids $5$). Depuis $A$ : $\text{dist}(A)=0$. On extrait $A$, on relâche $B$ ($\text{dist}(B)=4$) et $C$ ($\text{dist}(C)=1$). On extrait $C$ (distance minimale $1$), on relâche $B$ via $C$ : $\text{dist}(C)+2=3<4$, donc $\text{dist}(B)=3$ ; on relâche $D$ via $C$ : $\text{dist}(D)=1+5=6$. On extrait $B$ (distance $3$), on relâche $D$ via $B$ : $3+1=4<6$, donc $\text{dist}(D)=4$. Résultat final : $\text{dist}(A,B,C,D)=(0,3,1,4)$.

5. Pourquoi Dijkstra échoue avec des poids négatifs

Dijkstra suppose qu'une fois un sommet extrait de la file (sa distance finalisée), aucune amélioration future n'est possible — ce qui n'est vrai que si tous les poids restants sont positifs (toute relaxation ultérieure ne peut qu'augmenter une distance). Avec des poids négatifs, un chemin découvert plus tard pourrait être plus court, invalidant cette hypothèse. Pour des graphes avec poids négatifs (sans cycle de poids négatif), on utilise l'algorithme de Bellman-Ford ($O(nm)$, plus lent mais correct dans ce cas).

6. Algorithme de Floyd-Warshall (tous les plus courts chemins)

Pour calculer les plus courts chemins entre toutes les paires de sommets, l'algorithme de Floyd-Warshall utilise une programmation dynamique en $O(n^3)$ :

où $d_k[i][j]$ est la plus courte distance de $i$ à $j$ en n'utilisant que les sommets intermédiaires $\{1,\dots,k\}$. C'est avantageux par rapport à $n$ exécutions de Dijkstra ($O(n(n+m)\log n)$) lorsque le graphe est dense ($m$ proche de $n^2$).

7. Récapitulatif

|---|---|---|