Algorithmique · Écoles d'ingénieurs — ENSIAS

Algorithmes sur les graphes : Plus courts chemins et arbres couvrants

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Plus court chemin (Single Source Shortest Path) :
- Dijkstra : Utilise une file de priorité. Complexité $O((V+E) \log V)$ . Ne gère pas les poids négatifs.
- Bellman-Ford : Relaxation de toutes les arêtes $V-1$ fois. Complexité $O(V \cdot E)$ . Détecte les cycles absorbants.
Arbre couvrant minimal (MST) :
- Prim : Croissance d'un arbre à partir d'un sommet.
- Kruskal : Tri des arêtes par poids croissant, ajout sans créer de cycle (Union-Find).

Méthodes à maîtriser

Relaxation : Si $dist[u] + w(u, v) < dist[v]$ , alors $dist[v] = dist[u] + w(u, v)$ .
Dijkstra : Maintenir un tableau dist initialisé à $\infty$ et une file de priorité.
Kruskal : Trier les arêtes, utiliser une structure Union-Find pour vérifier l'absence de cycle.

Exemples corrigés

Dijkstra : Sur un graphe à 4 sommets, mettre à jour les distances à chaque extraction du sommet de poids minimal.
Kruskal : Trier les arêtes $(A,B,2), (B,C,3), (A,C,5)$ . Choisir $(A,B)$ puis $(B,C)$ .

Erreurs fréquentes

Appliquer Dijkstra sur un graphe avec des poids négatifs.
Oublier de vérifier la création d'un cycle dans Kruskal.
Confondre la complexité de Dijkstra avec/sans file de priorité (Fibonacci heap).

L'essentiel du cours

Plus court chemin (Single Source Shortest Path) :
- Dijkstra : Utilise une file de priorité. Complexité $O((V+E) \log V)$. Ne gère pas les poids négatifs.
- Bellman-Ford : Relaxation de toutes les arêtes $V-1$ fois. Complexité $O(V \cdot E)$. Détecte les cycles absorbants.
Arbre couvrant minimal (MST) :
- Prim : Croissance d'un arbre à partir d'un sommet.
- Kruskal : Tri des arêtes par poids croissant, ajout sans créer de cycle (Union-Find).

Méthodes à maîtriser

Relaxation : Si $dist[u] + w(u, v) < dist[v]$, alors $dist[v] = dist[u] + w(u, v)$.
Dijkstra : Maintenir un tableau dist initialisé à $\infty$ et une file de priorité.
Kruskal : Trier les arêtes, utiliser une structure Union-Find pour vérifier l'absence de cycle.

Exemples corrigés

Dijkstra : Sur un graphe à 4 sommets, mettre à jour les distances à chaque extraction du sommet de poids minimal.
Kruskal : Trier les arêtes $(A,B,2), (B,C,3), (A,C,5)$. Choisir $(A,B)$ puis $(B,C)$.

Erreurs fréquentes

Appliquer Dijkstra sur un graphe avec des poids négatifs.
Oublier de vérifier la création d'un cycle dans Kruskal.
Confondre la complexité de Dijkstra avec/sans file de priorité (Fibonacci heap).

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Algorithmes sur les graphes : Plus courts chemins et arbres couvrants

1/4

Quel algorithme est le plus adapté pour un graphe avec des poids négatifs mais sans cycle négatif ?

❓ Questions fréquentes

Kifach n-l9a l'arbre couvrant b'Kruskal ila kano bzaf d'les arêtes ?

Trie toutes les arêtes par ordre croissant de poids.
Prends l'arête la plus légère.
Ajoute-la si elle ne relie pas deux sommets déjà connectés (pas de cycle).
Répète jusqu'à avoir $V-1$ arêtes.

💡 À retenir : Kruskal = Tri + Union-Find.

Trie toutes les arêtes par ordre croissant de poids.
Prends l'arête la plus légère.
Ajoute-la si elle ne relie pas deux sommets déjà connectés (pas de cycle).
Répète jusqu'à avoir $V-1$ arêtes.

💡 À retenir : Kruskal = Tri + Union-Find.

Kifach n3ref wach n-khdem b Dijkstra awla Bellman-Ford ?

Vérifie les poids des arcs.
S'ils sont tous positifs ou nuls, Dijkstra est plus rapide et efficace.
S'il y a des poids négatifs, Dijkstra ne fonctionne pas, tu dois utiliser Bellman-Ford.

💡 À retenir : Dijkstra = poids $\ge 0$ ; Bellman-Ford = poids quelconques (sans cycle négatif).

Vérifie les poids des arcs.
S'ils sont tous positifs ou nuls, Dijkstra est plus rapide et efficace.
S'il y a des poids négatifs, Dijkstra ne fonctionne pas, tu dois utiliser Bellman-Ford.

💡 À retenir : Dijkstra = poids $\ge 0$ ; Bellman-Ford = poids quelconques (sans cycle négatif).

Chno hiya l'utilité dyal l'arbre couvrant minimal ?

L'arbre couvrant minimal sert à connecter tous les sommets d'un graphe avec le coût total le plus faible possible. C'est utilisé dans les réseaux (câblage, routes) pour minimiser les dépenses tout en assurant la connectivité.

💡 À retenir : MST = Connectivité totale à coût minimal.

Est-ce que Dijkstra garantit toujours le plus court chemin ?

Oui, à condition que tous les poids des arcs soient positifs. Si un poids est négatif, l'algorithme peut "manquer" un chemin plus court découvert plus tard.

💡 À retenir : Dijkstra est un algorithme glouton qui fait des choix définitifs.

Comment détecter un cycle absorbant avec Bellman-Ford ?

Après avoir fait $V-1$ relaxations, refais une $V$ -ième itération. Si une distance diminue encore, c'est qu'il existe un cycle absorbant.

💡 À retenir : Une $V$ -ième relaxation réussie = cycle négatif détecté.

Après avoir fait $V-1$ relaxations, refais une $V$-ième itération. Si une distance diminue encore, c'est qu'il existe un cycle absorbant.

💡 À retenir : Une $V$-ième relaxation réussie = cycle négatif détecté.

Est-ce que l'arbre couvrant est unique ?

Non, si plusieurs arêtes ont le même poids, il peut y avoir plusieurs arbres couvrants minimaux différents.

💡 À retenir : Le coût minimal est unique, mais la structure de l'arbre peut varier.

Wach l'algorithme de Prim khasso y-bda mn sommet mou3ayan ?

Non, tu peux commencer par n'importe quel sommet. Le résultat final (le coût total) sera le même pour un graphe connexe.

💡 À retenir : Prim est indépendant du sommet de départ.

Quelle est la complexité de Kruskal ?

Elle est dominée par le tri des arêtes : $O(E \log E)$ ou $O(E \log V)$ .

💡 À retenir : Kruskal est très efficace pour les graphes creux.

Elle est dominée par le tri des arêtes : $O(E \log E)$ ou $O(E \log V)$.

💡 À retenir : Kruskal est très efficace pour les graphes creux.

Pourquoi on utilise une file de priorité dans Dijkstra ?

Pour extraire rapidement le sommet non visité ayant la plus petite distance actuelle, ce qui optimise la recherche.

💡 À retenir : Sans file de priorité, la complexité monte à $O(V^2)$ .

Pour extraire rapidement le sommet non visité ayant la plus petite distance actuelle, ce qui optimise la recherche.

💡 À retenir : Sans file de priorité, la complexité monte à $O(V^2)$.

Est-ce que Bellman-Ford peut trouver le plus court chemin dans un graphe non orienté ?

Oui, à condition de transformer chaque arête non orientée en deux arcs orientés de poids identiques.

💡 À retenir : Bellman-Ford s'adapte aux graphes non orientés.

Qu'est-ce qu'une structure Union-Find ?

C'est une structure qui gère des ensembles disjoints. Elle permet de savoir si deux sommets sont déjà dans la même composante connexe (pour éviter les cycles).

💡 À retenir : Indispensable pour Kruskal.

L'algorithme de Dijkstra est-il un algorithme glouton ?

Oui, car il choisit à chaque étape le sommet le plus proche sans revenir sur ses choix précédents.

💡 À retenir : Les algorithmes gloutons font des choix locaux optimaux.

✍️ Exercices type examen national

Exercice 1

Soit un graphe $G=(V, E)$ avec $V=\{A, B, C, D\}$ et les arêtes pondérées : $(A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,D,8)$ .

Appliquer l'algorithme de Dijkstra pour trouver le plus court chemin de A vers D.
Donner l'arbre couvrant minimal par l'algorithme de Prim en partant de A.

Exercice 1

Soit un graphe $G=(V, E)$ avec $V={A, B, C, D}$ et les arêtes pondérées : $(A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,D,8)$.

Appliquer l'algorithme de Dijkstra pour trouver le plus court chemin de A vers D.
Donner l'arbre couvrant minimal par l'algorithme de Prim en partant de A.

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Algorithmique

Introduction à l'algorithmique et complexité Structures de données linéaires : Listes, Piles et Files Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Arbres binaires et arbres de recherche Structures de données avancées : Tas (Heaps) et Files de priorité Tables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Programmation dynamique Algorithmes gloutons Introduction à la théorie de la complexité (P vs NP)