L'essentiel à connaître
Un graphe est un ensemble de sommets reliés par des arêtes. C'est l'outil parfait pour modéliser des réseaux de transport, des relations sociales ou des architectures réseau. Les graphes peuvent être orientés (les flèches ont un sens) ou non orientés, et les arêtes peuvent être pondérées (chaque route a un coût, comme la distance ou le temps).
La recherche du plus court chemin est l'un des problèmes les plus classiques. L'algorithme de Dijkstra est la référence pour trouver le chemin le plus court depuis un sommet vers tous les autres dans un graphe aux poids positifs. Si les poids peuvent être négatifs, Dijkstra échoue et on doit utiliser l'algorithme de Bellman-Ford, plus lent mais plus robuste, capable de détecter des cycles de poids négatifs.
Définition : Un graphe G = (V, E) est composé d'un ensemble V de sommets (vertices) et d'un ensemble E d'arêtes (edges).
À retenir : Dijkstra est un algorithme glouton (greedy) qui privilégie toujours le sommet le plus proche connu.
Les points clés
Pour réussir ce quiz, n'oublie pas les complexités. Dijkstra avec une file de priorité s'exécute en O((V+E) log V). Bellman-Ford est en O(V * E), ce qui est nettement plus lourd. Il existe aussi l'algorithme de Floyd-Warshall pour trouver les plus courts chemins entre TOUTES les paires de sommets, avec une complexité de O(V^3).
Un autre concept clé est celui de l'Arbre Couvrant de Poids Minimum (ACPM), souvent résolu par les algorithmes de Kruskal ou Prim. Attention à ne pas confondre le plus court chemin (Dijkstra) et l'ACPM (Kruskal) : le premier cherche à minimiser la distance depuis une source, le second cherche à relier tous les sommets avec le coût total minimal sans créer de cycle.
Formule : Relation d'Euler pour les graphes planaires : V - E + F = 2 (où F est le nombre de faces).
Piège classique : Dijkstra ne fonctionne jamais avec des arêtes de poids négatif. Il risque de boucler ou de donner un résultat erroné.
Quiz : Teste tes connaissances
Question 1 : Quel algorithme est le plus efficace pour trouver le plus court chemin dans un graphe aux poids tous positifs ?
Réponse : B. Dijkstra est optimisé pour les poids positifs. Bellman-Ford (A) fonctionnerait mais serait beaucoup plus lent inutilement.
Question 2 : Que peut détecter Bellman-Ford que Dijkstra ne peut pas ?
Réponse : D. Si un cycle a une somme de poids négative, on peut réduire la distance à l'infini en tournant dedans. Bellman-Ford repère cette anomalie.
Question 3 : Dans un graphe non orienté, comment appelle-t-on le nombre d'arêtes reliées à un sommet ?
Réponse : A. Le degré d'un sommet est le compte de ses voisins directs. L'ordre (B) désigne le nombre total de sommets dans le graphe.
Question 4 : Quel algorithme permet de trouver les plus courts chemins entre toutes les paires de sommets simultanément ?
Réponse : C. Floyd-Warshall utilise la programmation dynamique pour calculer une matrice complète des distances en O(V^3).
Question 14 : Quelle structure de données est souvent utilisée pour optimiser l'algorithme de Dijkstra ?
Réponse : B. La file de priorité permet d'extraire rapidement le sommet ayant la plus petite distance provisoire, ce qui accélère grandement l'algorithme.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
- Générateur de Mind Maps : visualise et organise tes idées avec des cartes mentales générées automatiquement.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !