Graphes — 06 — Dijkstra : le plus court chemin pondéré
L'algorithme de Dijkstra : trouver le plus court chemin dans un graphe à poids positifs avec une file de priorité. Principe, code, complexité et limite des poids négatifs.
Articles : plus court chemin
3 articles sur le thème "plus court chemin".
Graphes — 07 — Bellman-Ford et A* : poids négatifs et recherche heuristique
Deux variantes du plus court chemin : Bellman-Ford pour les poids négatifs et la détection de cycles négatifs, et A* qui guide Dijkstra avec une heuristique.
Graphes — 02 — Le parcours en largeur (BFS)
Le parcours en largeur (BFS) : explorer un graphe niveau par niveau avec une file, trouver le plus court chemin en nombre d'arêtes, et ses usages réels.