Dans Dijkstra, la relaxation de l'arête (u, v) de poids w consiste à :

Mettre à jour dist[v] si dist[u] + w < dist[v]

DFS est particulièrement utile pour :

Détecter les cycles dans un graphe

Que se passe-t-il si on oublie de marquer les sommets comme visités dans BFS ?

L'algorithme boucle indéfiniment dans un graphe avec cycle

Quelle initialisation est utilisée dans Dijkstra ?

dist[source] = 0, dist[autres] = +∞

Quelle est la complexité de BFS et DFS avec des listes d'adjacence ?

O(n + m). BFS et DFS visitent chaque sommet (n) et chaque arête (m) exactement une fois avec des listes d'adjacence, soit O(n + m).

Dans Dijkstra, la relaxation de l'arête (u, v) de poids w consiste à :

Mettre à jour dist[v] si dist[u] + w < dist[v]. La relaxation vérifie si passer par u améliore le chemin vers v : si dist[u] + w < dist[v], on met à jour dist[v] = dist[u] + w.

DFS est particulièrement utile pour :

Détecter les cycles dans un graphe. DFS peut détecter un cycle : si lors du parcours on atteint un sommet déjà en cours de visite (dans la pile d'appels), c'est qu'il y a un cycle.

Que se passe-t-il si on oublie de marquer les sommets comme visités dans BFS ?

L'algorithme boucle indéfiniment dans un graphe avec cycle. Sans marquage des sommets visités, un sommet peut être enfilé plusieurs fois. Dans un graphe avec cycle, cela provoque une boucle infinie.

Quelle initialisation est utilisée dans Dijkstra ?

dist[source] = 0, dist[autres] = +∞. On initialise la distance de la source à 0 (le coût pour aller de la source à elle-même) et toutes les autres distances à +∞ (pas encore de chemin connu).

Pour un graphe non pondéré, quel algorithme utiliser pour le plus court chemin ?

BFS suffit. Pour un graphe non pondéré, BFS trouve directement le plus court chemin en nombre d'arêtes. Dijkstra fonctionnerait aussi mais est inutilement complexe dans ce cas.

NSI (Spé) — Algorithmique

Algorithmes sur les graphes

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

Une file. BFS utilise une file (FIFO) pour explorer les sommets par distance croissante au sommet de départ.

Q: Le parcours en profondeur (DFS) utilise :

Une pile (ou la récursivité). DFS utilise une pile (LIFO) en version itérative, ou la pile d'appels de fonctions en version récursive, pour explorer le plus loin possible avant de revenir en arrière.

Q: L'algorithme de Dijkstra ne fonctionne pas correctement avec :

Des poids négatifs. Dijkstra suppose que tous les poids sont positifs ou nuls. Avec des poids négatifs, un sommet déjà visité pourrait avoir un chemin plus court découvert plus tard, faussant le résultat.

Q: BFS trouve le plus court chemin en :

Nombre d'arêtes (graphe non pondéré). BFS explore les sommets par couches concentriques (distance 1, puis 2, etc.), trouvant ainsi le chemin avec le moins d'arêtes dans un graphe non pondéré.

Q: Quelle est la complexité de BFS et DFS avec des listes d'adjacence ?

O(n + m). BFS et DFS visitent chaque sommet (n) et chaque arête (m) exactement une fois avec des listes d'adjacence, soit O(n + m).

Q: DFS est particulièrement utile pour :

Détecter les cycles dans un graphe. DFS peut détecter un cycle : si lors du parcours on atteint un sommet déjà en cours de visite (dans la pile d'appels), c'est qu'il y a un cycle.

Q: Que se passe-t-il si on oublie de marquer les sommets comme visités dans BFS ?

L'algorithme boucle indéfiniment dans un graphe avec cycle. Sans marquage des sommets visités, un sommet peut être enfilé plusieurs fois. Dans un graphe avec cycle, cela provoque une boucle infinie.

Q: Quelle initialisation est utilisée dans Dijkstra ?

dist[source] = 0, dist[autres] = +∞. On initialise la distance de la source à 0 (le coût pour aller de la source à elle-même) et toutes les autres distances à +∞ (pas encore de chemin connu).

Q: Pour un graphe non pondéré, quel algorithme utiliser pour le plus court chemin ?

BFS suffit. Pour un graphe non pondéré, BFS trouve directement le plus court chemin en nombre d'arêtes. Dijkstra fonctionnerait aussi mais est inutilement complexe dans ce cas.

Parcours en largeur (BFS), parcours en profondeur (DFS), algorithme de Dijkstra pour les plus courts chemins

Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub

Résumé

Le parcours en largeur (BFS, Breadth-First Search) explore un graphe niveau par niveau en utilisant une file. Il permet de trouver le plus court chemin en nombre d'arêtes entre deux sommets. Par exemple, dans un réseau social, BFS trouve la plus courte chaîne d'amis entre deux personnes. Le parcours en profondeur (DFS, Depth-First Search) explore un graphe en allant le plus loin possible avant de revenir en arrière, en utilisant une pile (ou la récursivité). Il est utile pour détecter les cycles et les composantes connexes. L'algorithme de Dijkstra trouve le plus court chemin pondéré (somme des poids minimale) depuis un sommet source vers tous les autres. Par exemple, il calcule l'itinéraire le plus rapide sur une carte routière. Dijkstra ne fonctionne qu'avec des poids positifs et utilise un ensemble de sommets visités qu'il étend progressivement.

Thème complet

Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale

Ce thème dans une autre classe

Seconde — Mathématiques

Algorithmique et programmation

Première — Mathématiques

Algorithmique et programmation Python

Première — Maths (Spé)

Algorithmique et programmation Python

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

Questions fréquentes

Les points clés à retenir sur Algorithmes sur les graphes, extraits du quiz de révision.

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

Réponse : Une file

BFS utilise une file (FIFO) pour explorer les sommets par distance croissante au sommet de départ.

Le parcours en profondeur (DFS) utilise :

Réponse : Une pile (ou la récursivité)

DFS utilise une pile (LIFO) en version itérative, ou la pile d'appels de fonctions en version récursive, pour explorer le plus loin possible avant de revenir en arrière.

L'algorithme de Dijkstra ne fonctionne pas correctement avec :

Réponse : Des poids négatifs

Dijkstra suppose que tous les poids sont positifs ou nuls. Avec des poids négatifs, un sommet déjà visité pourrait avoir un chemin plus court découvert plus tard, faussant le résultat.

BFS trouve le plus court chemin en :

Réponse : Nombre d'arêtes (graphe non pondéré)

BFS explore les sommets par couches concentriques (distance 1, puis 2, etc.), trouvant ainsi le chemin avec le moins d'arêtes dans un graphe non pondéré.

Résumé

Questions fréquentes

Les points clés à retenir sur Algorithmes sur les graphes, extraits du quiz de révision.

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

Réponse : Une file

BFS utilise une file (FIFO) pour explorer les sommets par distance croissante au sommet de départ.

Le parcours en profondeur (DFS) utilise :

Réponse : Une pile (ou la récursivité)

DFS utilise une pile (LIFO) en version itérative, ou la pile d'appels de fonctions en version récursive, pour explorer le plus loin possible avant de revenir en arrière.

L'algorithme de Dijkstra ne fonctionne pas correctement avec :

Réponse : Des poids négatifs

Dijkstra suppose que tous les poids sont positifs ou nuls. Avec des poids négatifs, un sommet déjà visité pourrait avoir un chemin plus court découvert plus tard, faussant le résultat.

BFS trouve le plus court chemin en :

Réponse : Nombre d'arêtes (graphe non pondéré)

BFS explore les sommets par couches concentriques (distance 1, puis 2, etc.), trouvant ainsi le chemin avec le moins d'arêtes dans un graphe non pondéré.

Algorithmes sur les graphes

Résumé

Parcours en largeur (BFS)

Parcours en profondeur (DFS)

Algorithme de Dijkstra

Comparaison BFS / DFS / Dijkstra

Quiz - Algorithmes sur les graphes

Ce thème dans une autre classe

Articles utiles

Questions fréquentes

Algorithmes sur les graphes

Résumé

Parcours en largeur (BFS)

Parcours en profondeur (DFS)

Algorithme de Dijkstra

Comparaison BFS / DFS / Dijkstra

Quiz - Algorithmes sur les graphes

Ce thème dans une autre classe

Articles utiles

Questions fréquentes