10 documents tagués avec "graph"

Plus courts chemins depuis une source avec arêtes négatives et détection des cycles négatifs accessibles.

Plus courts chemins depuis une source avec des poids d’arêtes non négatifs.

Programmation dynamique pour les plus courts chemins entre toutes les paires et la détection des cycles de poids négatif.

Forêts couvrantes minimums obtenues par tri des arêtes et union d'ensembles disjoints.

Construction progressive d'un arbre couvrant minimum par l'arête admissible la plus légère d'une coupe.

Une carte orientée problèmes pour choisir entre parcours, plus courts chemins et arbres couvrants minimums.

La propriété de la coupe relie les choix d'arêtes sûrs de Prim et de Kruskal.

Une lecture des plus courts chemins par les récurrences, reliée aux algorithmes propres aux graphes.

Parcours de graphe par couches et plus courts chemins en nombre d’arêtes.

Parcours de graphe fondé sur une pile, structure parentale et garanties propres à DFS.