Please enable JavaScript.

Coggle requires JavaScript to display documents.

Graphes (Partie 2) (Recherche de plus courts chemins (Trouver tous les…

- - - - :timer_clock: Temps en Θ(n+m)
      - :star: Lorsque le graphe est acyclique, il suffit de parcourir les noeuds dans un ordre
        topologique une seule fois.
      - :star: Lors de ce parcours, il suffit de relâcher (une seule fois) l’arc (u,v) pour chaque
        noeud v adjacent au noeud courant u
    - - :timer_clock: Temps en Θ(n2) mais tous les poids doivent être ≥ 0
      - Problème à résoudre
        
        On a un graphe (possiblement) orienté valué G(S,A,w) et un sommet source s de S. On veut obtenir le plus court chemin entre s et chacun des sommets de S \ {s}
      - Approche gloutonne (vorace) utilisée
        
        1)On trouve d’abord le noeud u* le plus près se s
        
        2)s’il n’existe pas de poids négatifs, u est le noeud adjacent à s dont w(s,u) est minimal !!
        
        3)Ensuite on ajoute u* à l’ensemble des noeuds solutionnés les plus près de s
        
        4)Après i itérations, les i noeuds les plus près de s
        formeront un arbre Ti
        
        5)Relâchement -> consiste à mettre à jour, pour certains noeuds u de S, un majorant
        (une borne supérieure) d(u) de la distance du plus court chemin allant de s à u
        
        Le relâchement pour l’arc (v,u) est la séquence d’opérations suivante:
        SI d(v) + w(v,u) < d(u) ALORS
        d(u) = d(v) + w(v,u) ;//une estimation moins pessimiste de d(u) a été trouvée
        p(u) = v; //le prédécesseur de u a changé
        //sinon ne rien faire car on n’a pas trouvé un chemin plus court vers u
      - :star: Consiste simplement à construire cette séquence T0, T1, …, Tn-1 d’arbres de noeuds solutionnés
      - :star: Donc, lorsque Tn-1 est obtenu, pour tout v dans S, on a que d(v) est égal à
        la distance du plus court chemin de s à v et le prédécesseur de v sur ce
        chemin est donné par p(v)
    - - :timer_clock: Temps en Θ(nm) et permet les poids négatifs
      - :star: L’algorithme Bellman-Ford fonctionne avec des poids négatifs mais au prix
        d’un temps d’exécution plus long que celui de Dijkstra
  - - - :star: Soit un graphe G =(S,A,w), nous disons qu’une séquence de noeuds est selon un
        ordre topologique de G ssi pour tout arc (u,v) de G, u précède v dans cette
        séquence
      - Algorithme
        
        1)Pour trier un graphe acyclique G(S,A,w) dans un ordre topologique, nous pouvons d’abord identifier tous les noeuds dont l’arité d’entrée est nulle
        
        2)Ces noeuds doivent se trouver en première position dans le tableau trié T (l’ordre relatif entre ces noeuds n’a pas d’importance)
        
        3)Après avoir placé ces noeuds dans T, il suffit d’enlever les arcs sortant de ces noeuds.
        Cela décroît alors l’arité d’entrée des noeuds adjacents aux noeud placés dans T
        
        3)On recommence avec le graphe résultant
      - :timer_clock: Temps en O(|S|2) en pire cas, car après avoir
        enlever les noeuds d’arité d’entrée nulle, il faut visiter tous les autres noeuds
      - :timer_clock: :warning: Astuce pour accélérer l’algorithme: ne visiter que les noeuds adjacents aux noeuds
        enlevés! Cela donne l’algorithme à la page suivante
      - :timer_clock:TriTopologique() s’exécute en Θ(n+m).
    - - :star: Permet de trouver la longueur du plus court chemin entre toutes les paires de sommets d’un graphe orienté valué (pondéré)
      - :star: Donne la distance du plus court chemin entre toutes les paires de noeuds possibles d’un graphe
      - :warning: Un léger ajout à cet algorithme nous permet d’obtenir également la séquence de noeuds utilisés par les plus courts chemins