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 : graphes
9 articles sur le thème "graphes".
Graphes — 01 — Représenter un graphe : liste vs matrice d'adjacence
Les deux façons de stocker un graphe en mémoire : liste d'adjacence et matrice d'adjacence. Leurs coûts en temps et en mémoire, et comment choisir selon la densité.
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 — 03 — Le parcours en profondeur (DFS)
Le parcours en profondeur (DFS) : explorer au plus loin avant de revenir, en version récursive et itérative avec pile, sa complexité et ses applications.
Graphes — 00 — Modéliser un problème en graphe
Introduction aux graphes : sommets et arêtes, vocabulaire (orienté, pondéré, cyclique), et pourquoi voir un problème comme un graphe ouvre des solutions toutes faites.
Graphes — 08 — Les graphes dans le vrai code
Synthèse de la série graphes : reconnaître un problème de graphe dans du code réel (dépendances, réseaux, recommandations) et choisir le bon algorithme.
Graphes — 05 — Le tri topologique : ordonner des dépendances
Le tri topologique : ordonner les sommets d'un DAG pour respecter toutes les dépendances. Les deux méthodes (Kahn par degrés entrants, et DFS), et leurs usages.
Graphes — 04 — Détection de cycle et graphes acycliques (DAG)
Détecter un cycle avec DFS, dans un graphe orienté (coloration des sommets) et non orienté. Ce qu'est un DAG et pourquoi cette structure est si importante.
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.