Algorithmes fondamentaux en théorie des graphes: chemins courts et connectivité
0x61 Chemins les plus courts
Algorithmes source unique
Algorithme de Dijkstra : Pour un graphe avec des poids d'arêtes non négatifs, cet algorithme calcule les distances les plus courtes depuis un sommet source. Il fonctionne par sélection gloutonne : à chaque itération, le sommet non visité avec la distance la plus faible est choisi, puis on m ...
Publié le 21 juillet à 04h05
Flots en réseaux
Flot maximum
Définition
On cherche à acheminer la plus grande quantité possible de ressources d'une source S vers un puits T dans un réseau.
Principe
L'idée initiale de chercher un chemin positif de S à T et d'y augmenter le flot est incomplète. On ajoute des arcs résiduels (arcs retour) pour permettre des annulations partielles, un mécanisme d ...
Publié le 25 juin à 20h55