Algorithmes appliqués aux graphes

Voici quelques algorithmes qui s'appliquent au domaine des graphes. Nous allons nous intéresser à certains d'entre-eux (vous pouvez cliquer sur les liens pour plus de détails).

  • Parcourir un graphe
  • Chemins et circuits
    • Détecter la simple présence d'un chemin entre 2 sommets
    • Détecter un chemin de longueur déterminée entre 2 sommets
    • Calculer le nombre de longueur déterminée (>1) entre 2 sommets
    • Calculer la matrice M ou M' : Algorithme de Warshall, complexité de Ordre de grandeur(n3).
    • Détecter un circuit dans un graphe
    • Détecter un circuit passant par un sommet donné
    • Détecter un circuit passant par un arc donné
  • Rechercher un ou plusieurs chemins extrémaux des graphes pondérés (les plus courts ou les plus longs)
    • Algorithme de Bellman-Kalaba (pas de circuits), complexité de Ordre de grandeur(n2).
    • Algorithme de Moore-Dijkstra (circuits nécessaires, poids positifs ou nuls), complexité de Ordre de grandeur(n2).
    • Algorithme de Ford-Bellman (avec ou sans circuits, détection de circuits absorbants, poids quelconques), complexité de Ordre de grandeur(n3).
    • Heusistique A* (avec ou sans circuits, bornes, et sommet destination pré-déterminé)
    • Algorithme de Floyd-Warshall (accepte les poids négatifs, mais pas de cycle strictement négatif)
    • Algorithme de Ford-Dantzig (graphe orienté, avec ou sans circuit, poids positifs et négatifs)
  • Arbres couvrant (ARPM[1], ou ACM[2])
    • Algorithme de Kruskal (graphe connexe, valué, non orienté)
    • Algorithme de Prim (graphe connexe, valué, non orienté)
  • Flux extémaux (minimum ou maximum)
    • Algorithme de Ford-Fulkerson
    • Algorithme de Edmonds-Karp
    • Algorithme de flux bloquant de Dinitz
  • Divers
    • Construire la fermeture transitive d'un graphe orienté ou non orienté
    • Construire les composantes simplement connexes d'un graphe (via DFS), complexité de Ordre de grandeur(m+n).
    • Construire les composantes fortement connexes d'un graphe
    • Décomposer en niveaux. (sans circuit), complexité de Ordre de grandeur(n2).
    • Aide à la décision multicritère : ELECTRE

 

Document créé le 27/11/09 22:45, dernière modification le 22/08/17 07:06
Source du document imprimé : https://www.gaudry.be/graphes-algo.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.

Notes

  1.  ARPM : Arbre Recouvrant de Poids Minimum

  2.  ACM : Arbre Couvrant Minimum