Algorithmes de graphes

Commencez par caractériser le graphe : orienté ou non, pondéré ou non, creux ou dense, et susceptible ou non de contenir des arêtes négatives ou des cycles. Précisez ensuite le résultat attendu : accessibilité, un chemin, toutes les distances ou un sous-graphe de connexion.

Carte de décision

Problème	Conditions	Algorithme	Temps avec une représentation courante
Accessibilité / structure	listes d'adjacence générales	DFS ou BFS	$O(V+E)$
Chemin avec le moins d'arêtes	non pondéré / coûts égaux	BFS	$O(V+E)$
Plus courts chemins à source unique	poids non négatifs	Dijkstra	$O((V+E)\log V)$
Plus courts chemins à source unique	arêtes négatives autorisées	Bellman–Ford	$O(VE)$
Plus courts chemins entre toutes les paires	graphe dense ou $V$ modeste	Floyd–Warshall	$O(V^3)$
Arbre couvrant minimum	graphe non orienté pondéré	Prim	$O(E\log V)$
Arbre couvrant minimum	liste d'arêtes triable	Kruskal	$O(E\log E)$

Distinguer les objectifs

Un arbre des plus courts chemins minimise les distances entre la source et chaque sommet. Un arbre couvrant minimum minimise le poids total nécessaire pour relier tous les sommets. Aucun de ces objectifs n'implique l'autre, même si Dijkstra et Prim utilisent tous deux une file de priorité.

La représentation compte

Les listes d'adjacence occupent $O(V+E)$ et conviennent aux graphes creux. Une matrice d'adjacence occupe $O(V^2)$, fournit un accès aux arêtes en temps constant et peut simplifier les algorithmes toutes paires sur les graphes denses. Une complexité annoncée sans ce choix de représentation est incomplète.

Lire les contrats

V compte tous les sommets, même isolés ; E compte les arêtes (une liste d'adjacence non orientée stocke deux entrées par arête). Les bornes du tableau pour les tas supposent des graphes simples ; un tas paresseux sur un multigraphe peut demander log E plutôt que log V. Comptez l'initialisation O(V) quand E est nul ou que de nombreux sommets sont isolés. BFS minimise le coût total pour des poids égaux non négatifs, pas pour des coûts négatifs.

Une arête absente n'est pas une arête de poids nul. Représentez une distance inaccessible par l'infini et distinguez l'absence de chemin du chemin de longueur nulle de la source à elle-même. Un cycle négatif n'affecte une requête que si la source l'atteint et qu'il atteint la destination. Pour les marches non orientées, une arête négative accessible permet déjà un aller-retour de coût arbitrairement négatif ; les MST évitent ce problème puisque leurs sorties sont acycliques.

Dans le triangle A—B:2, B—C:2, A—C:3, l'MST coûte 4, mais son chemin de A à C coûte 4 au lieu de la distance minimale 3. L'arbre des plus courts chemins enraciné en A coûte quant à lui 5 au total.

Sources

• MIT OpenCourseWare : introduction aux algorithmes
• Open Data Structures : graphes

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.