Algorithmes de graphes : parcours et plus courts chemins

Quelle structure de données utilise naturellement le parcours en largeur (BFS) ?

Le BFS enfile les voisins découverts et les traite dans l'ordre FIFO, garantissant une exploration niveau par niveau.

Vrai ou faux : dans un graphe non pondéré, le BFS depuis une source $s$ calcule les plus courts chemins (en nombre d'arêtes) vers tous les sommets atteignables.

Vrai. C'est la propriété clé du BFS : comme il explore niveau par niveau, la première fois qu'un sommet est atteint, c'est nécessairement par un chemin le plus court possible (en nombre d'arêtes).

Quelle structure de données est utilisée par l'algorithme de Dijkstra pour sélectionner efficacement le prochain sommet à traiter ?

Dijkstra utilise une file de priorité (typiquement un tas-min) pour extraire efficacement, à chaque étape, le sommet non encore traité ayant la plus petite distance provisoire.

Vrai ou faux : l'algorithme de Dijkstra fonctionne correctement même si certaines arêtes ont un poids négatif.

Faux. Dijkstra suppose que les distances ne peuvent qu'augmenter par relaxation future, ce qui échoue avec des poids négatifs (un chemin découvert plus tard pourrait raccourcir une distance déjà finalisée). Il faut alors utiliser Bellman-Ford.

Quelle est la complexité de l'algorithme de Floyd-Warshall pour calculer les plus courts chemins entre toutes les paires de sommets ?

Floyd-Warshall procède par programmation dynamique avec trois boucles imbriquées sur les $n$ sommets, donnant une complexité $O(n^3)$.

Pour un graphe avec $n$ sommets et $m$ arêtes représenté en liste d'adjacence, quelle est la complexité totale du DFS ou du BFS ?

Chaque sommet est visité (et marqué) une seule fois, et chaque arête est examinée au plus une ou deux fois (selon orientation), d'où une complexité linéaire $O(n+m)$ — optimale, puisqu'il faut au moins lire toute l'entrée.

Sur le graphe orienté $A\to B$ (poids 2), $A\to C$ (poids 5), $B\to C$ (poids 1), exécuter Dijkstra depuis $A$ et donner $\text{dist}(C)$.

Chemin direct $A\to C$ : coût $5$. Chemin $A\to B\to C$ : coût $2+1=3$, strictement meilleur. Dijkstra trouve donc $\text{dist}(C)=3$ (en passant par $B$).

Pourquoi préfère-t-on la liste d'adjacence à la matrice d'adjacence pour représenter un graphe creux (peu d'arêtes par rapport au nombre de sommets, $m=O(n)$) ?

Pour un graphe creux, $m=O(n)\ll n^2$, donc la liste d'adjacence ($O(n+m)=O(n)$ mémoire) est bien plus économe que la matrice d'adjacence ($O(n^2)$ mémoire, dont la plupart des cases seraient à $0$).

Vrai ou faux : le DFS peut être utilisé pour détecter la présence d'un cycle dans un graphe orienté.

Vrai. En suivant les couleurs des sommets pendant le parcours (blanc = non visité, gris = en cours d'exploration, noir = terminé), on détecte un cycle si l'on rencontre une arête menant vers un sommet gris (déjà sur la pile d'appels en cours) — c'est une arête de retour.

Expliquer pourquoi la complexité de Dijkstra avec une file de priorité par tas binaire est $O((n+m)\log n)$ plutôt que $O(nm)$.

Décomposition du coût total en deux parties.

Extractions : chaque sommet est extrait de la file de priorité exactement une fois (une fois sa distance finalisée, il n'y retourne jamais). Avec un tas binaire, chaque extraction du minimum coûte $O(\log n)$. Total pour les $n$ extractions : $O(n\log n)$.

Relaxations (mises à jour de priorité) : chaque arête du graphe est examinée au plus une fois (lors du traitement de son sommet de départ), et peut déclencher une mise à jour de la priorité du sommet d'arrivée dans le tas, coûtant $O(\log n)$ avec une implémentation adaptée (tas indexé permettant la mise à jour de clé). Total pour les $m$ arêtes : $O(m\log n)$.

Somme totale : $O(n\log n) + O(m\log n) = O((n+m)\log n)$.

C'est bien plus efficace que $O(nm)$ pour les graphes creux où $m=O(n)$ : on obtient $O(n\log n)$ au lieu de $O(n^2)$.

Sur le 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), exécuter Dijkstra depuis $A$ pas à pas et donner les distances finales pour $A,B,C,D$.

Initialisation : $\text{dist}(A)=0$, $\text{dist}(B)=\text{dist}(C)=\text{dist}(D)=+\infty$.

Étape 1 — extraire $A$ (distance $0$). Relâcher ses voisins : $\text{dist}(B)=\min(\infty,0+4)=4$ ; $\text{dist}(C)=\min(\infty,0+1)=1$.

Étape 2 — extraire $C$ (distance minimale $1$). Relâcher ses voisins : $\text{dist}(B)=\min(4,1+2)=\min(4,3)=3$ (amélioration !) ; $\text{dist}(D)=\min(\infty,1+5)=6$.

Étape 3 — extraire $B$ (distance minimale $3$). Relâcher ses voisins : $\text{dist}(D)=\min(6,3+1)=\min(6,4)=4$ (amélioration !).

Étape 4 — extraire $D$ (distance $4$). Aucun voisin sortant, rien à relâcher.

Résultat final : $\text{dist}(A)=0$, $\text{dist}(B)=3$, $\text{dist}(C)=1$, $\text{dist}(D)=4$. Le plus court chemin vers $D$ passe par $A\to C\to B\to D$ (coût $1+2+1=4$), pas par le chemin direct $A\to C\to D$ (coût $1+5=6$) ni par $A\to B\to D$ (coût $4+1=5$).

Démontrer pourquoi l'algorithme de Dijkstra peut donner un résultat incorrect en présence d'une arête de poids négatif, à l'aide d'un contre-exemple explicite.

Construction du contre-exemple. Graphe orienté : $A\to B$ (poids $1$), $A\to C$ (poids $4$), $C\to B$ (poids $-10$).

Exécution de Dijkstra depuis $A$ :
- Initialisation : $\text{dist}(A)=0$.
- Extraction de $A$ : relâcher $B$ ($\text{dist}(B)=1$) et $C$ ($\text{dist}(C)=4$).
- Extraction du sommet de distance minimale parmi les non traités : $B$ (distance $1<4$). On finalise $\text{dist}(B)=1$ et on ne le remet jamais en question (Dijkstra suppose qu'aucune amélioration future n'est possible pour un sommet déjà extrait).
- Extraction de $C$ (distance $4$) : on relâche $B$ via $C$, donnant $4+(-10)=-6$ — mais $B$ a déjà été extrait et finalisé à la valeur $1$, donc Dijkstra ignore cette amélioration (selon l'implémentation standard, qui ne retraite jamais un sommet déjà extrait).

Résultat erroné de Dijkstra : $\text{dist}(B)=1$.

Vrai plus court chemin : $A\to C\to B$, de coût $4+(-10)=-6$, strictement inférieur à $1$.

Conclusion : Dijkstra donne ici un résultat incorrect ($1$ au lieu de $-6$), car son hypothèse fondamentale (un sommet extrait ne peut plus être amélioré) est violée par la présence du poids négatif $-10$ sur l'arête $C\to B$. C'est exactement pourquoi Dijkstra exige des poids non négatifs, et pourquoi on utilise Bellman-Ford dans le cas contraire. $\square$

Vrai ou faux : l'algorithme de Bellman-Ford peut détecter la présence d'un cycle de poids négatif accessible depuis la source.

Vrai. Après les $n-1$ itérations habituelles de relaxation (suffisantes pour des plus courts chemins simples, sans cycle), Bellman-Ford effectue une itération supplémentaire : si une relaxation améliore encore une distance, c'est la preuve qu'un cycle de poids négatif est accessible (sinon le plus court chemin ne serait pas borné, n'existant simplement pas au sens usuel).

Justifier, dans le cadre de la programmation dynamique de Floyd-Warshall, la relation de récurrence $d_k[i][j]=\min\big(d_{k-1}[i][j],\,d_{k-1}[i][k]+d_{k-1}[k][j]\big)$.

Définition de $d_k[i][j]$. C'est la longueur du plus court chemin de $i$ à $j$ dans le graphe, en n'autorisant comme sommets intermédiaires (ni $i$ ni $j$ eux-mêmes, mais les sommets traversés en chemin) que ceux de l'ensemble $\{1,\dots,k\}$.

Disjonction de cas sur le rôle de $k$. Considérons le plus court chemin optimal de $i$ à $j$ n'utilisant que $\{1,\dots,k\}$ comme intermédiaires. Deux cas s'excluent mutuellement :

Cas 1 — ce chemin optimal n'utilise pas $k$ comme sommet intermédiaire. Alors il n'utilise en fait que $\{1,\dots,k-1\}$, donc sa longueur est exactement $d_{k-1}[i][j]$ (qui est déjà optimal pour cet ensemble plus restreint de sommets autorisés).

Cas 2 — ce chemin optimal utilise $k$ comme sommet intermédiaire (nécessairement une seule fois, car repasser deux fois par $k$ créerait un cycle, ce qui n'est jamais optimal avec des poids positifs ou en l'absence de cycle négatif). Le chemin se décompose alors en un trajet $i\to k$ et un trajet $k\to j$, chacun n'utilisant comme intermédiaires que $\{1,\dots,k-1\}$ (puisque $k$ n'apparaît qu'une fois, à la jonction). Pour que le chemin total soit optimal, chacun de ces deux sous-trajets doit aussi être optimal (principe d'optimalité de Bellman) : leur longueur totale est donc $d_{k-1}[i][k]+d_{k-1}[k][j]$.

Conclusion. Le plus court chemin global est le meilleur des deux cas :

Comparer, pour un graphe dense ($m=\Theta(n^2)$), la complexité de calculer les plus courts chemins entre toutes les paires de sommets via (a) $n$ exécutions de Dijkstra, contre (b) une seule exécution de Floyd-Warshall. Quelle méthode est préférable ?

Méthode (a) — $n$ exécutions de Dijkstra. Chaque exécution de Dijkstra depuis un sommet source coûte $O((n+m)\log n)$. En répétant pour chacun des $n$ sommets comme source :

Pour un graphe dense ($m=\Theta(n^2)$), cela devient $O\big(n\cdot n^2\cdot\log n\big)=O(n^3\log n)$.

Méthode (b) — Floyd-Warshall. Complexité directe $O(n^3)$, indépendamment de la densité du graphe.

Comparaison. Pour un graphe dense, $O(n^3)<O(n^3\log n)$ : Floyd-Warshall est asymptotiquement meilleur (et plus simple à implémenter, sans nécessiter de structure de tas).

Remarque complémentaire (cas creux). Pour un graphe creux ($m=O(n)$), la méthode (a) donnerait plutôt $O(n(n+n)\log n)=O(n^2\log n)$, ce qui est meilleur que $O(n^3)$ de Floyd-Warshall. Le choix optimal entre les deux méthodes dépend donc de la densité du graphe : Floyd-Warshall pour les graphes denses, $n$ exécutions de Dijkstra pour les graphes creux.