Les Graphes 2ième Partie Flashcards
Spécifications de l’Algorithme de Dijkstra
- Θ(n²)
- Pas de poids négatif
- Vorace
Principe de l’Algorithme de Dijkstra
- relâcher tous les arcs aux noeuds adjacents
- recommencer à partir du noeud adjacent relâché qui a la plus petite distance à S
Spécifications de l’Algorithme de Bellman-Ford
- Θ(nm)
- permet les poids négatifs
- il ne doit pas exister de cycle de longueur négative qui soit accessible depuis la source s.
Principe de l’Algorithme de Bellman-Ford
- relâcher tous les arcs |S|-1 fois maximum.
But de l’Algorithme de Dijkstra
Trouver les plus courts chemins d’une origine unique dans un graphe valué, les poids étants >=0.
But de l’Algorithme de Bellman-Ford
Trouver les plus courts chemins d’une origine unique dans un graphe valué, les poids pouvant être négatifs.
But de l’Algorithme de Bellman-Ford pour graphe orientés acyclique.
Trouver les plus courts chemins d’une origine unique dans un graphe orienté, valué, acyclique.
Spécifications de l’Algorithme de Bellman-Ford pour graphe orientés acyclique.
- Θ(n+m)
Principe de l’Algorithme de Bellman-Ford pour graphe orientés acyclique
- Faire un tri topologique
- Relâcher une fois tous les arcs dans l’ordre topologique des sommets.
Relâcher les arcs depuis un sommet v signifie :
- Mettre à jour la distance depuis l’origine de chaque sommet adjacents u si elle est meilleure que celle précédemment calculée.
- Mettre à jour le prédécesseur de u (pour v) si la distance est mise à jour.
Principe de l’Algorithme de TriTopologique (différent du parcours en profondeur)
- Retirer les noeuds d’arité d’entrée nulle et leur arcs sortants.
- Rechercher les nouveaux noeuds d’arité d’entrée nulle parmi les noeuds adjacents à ce qu’on vient de retirer.
- Recommencer jusqu’au dernier noeud
- L’ordre de retrait des noeud et le tri topologique
