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.