Théorie des graphes

Algorithme de chemin le plus court de Dijkstra

Étant donné un graphe et un sommet source dans le graphe, recherchez les chemins les plus courts allant de la source à tous les sommets du graphe donné.

L’algorithme de Dijkstra est très similaire à celui de Prim pour l'arbre couvrant minimum. Comme Prim, nous générons un S (arbre du plus court chemin) avec une source donnée en tant que racine.
Nous maintenons deux ensembles, l'un contient les sommets inclus dans l'arbre du plus court chemin (S), l'autre ensemble comprend les sommets non encore inclus dans l'arbre de plus court (T). À chaque étape de l'algorithme, nous trouvons un sommet qui se trouve dans l'autre ensemble (ensemble de non encore inclus) et qui a une distance minimale par rapport à la source.

Ci-dessous sont les étapes détaillées utilisées dans l'algorithme de Dijkstra pour trouver le chemin le plus court d'un sommet source simple à tous les autres sommets dans le graphe donné.

  1. Créer un ensemble S(arbre du plus court chemin) qui garde la trace des sommets inclus dans l'arbre de chemin le plus court, c.-à-d., dont la distance minimale de la source est calculée et finalisée. Initialement, cet ensemble est vide.
  2. Attribuez une valeur de distance à tous les sommets du graphique d'entrée. Initialisez toutes les valeurs de distance comme INFINI. Attribuez la valeur de distance 0 pour le sommet source afin qu'il soit sélectionné en premier.
  3. Tandis que l'ensemble S ne comprend pas tous les sommets
    • Choisissez un sommet u qui n'est pas dans l'ensemble S et qui a une valeur de distance minimale.
    • Incluez u à S.
    • Pour chaque successeur v de u, avec v dans T, faire
      • si la somme de la valeur de la distance de u (de la source) et le poids de l'arête u-v, est inférieure à la valeur de la distance de v
        • mettre à jour la valeur de distance de v.
                        import math
                        
                        
                        class Graphe():
                        
                            def __init__(self, noeuds):
                                self.matriceAdj = noeuds.copy()
                        
                            def Afficher(self, src, dist):
                                print("les chemins les plus courts allant de ", src, " est : ")
                                for noeud in range(len(self.matriceAdj)):
                                    print((noeud+1), "\t", dist[noeud])
                        
                            def minDistance(self, dist, S, T):
                        
                                # Initilaize minimum distance for next node
                                min = math.inf
                                min_index = -1
                        
                                for v in T:
                                    if dist[v-1] < min:
                                        min = dist[v-1]
                                        min_index = v-1
                        
                                # supprimer de T et ajouter dans S
                                T.remove(min_index+1)
                                S.append(min_index+1)
                                return min_index
                        
                            def dijkstra(self, src):
                        
                                dist = [math.inf] * len(self.matriceAdj)
                                precedence = [-1] * len(self.matriceAdj)
                                dist[src-1] = 0
                                precedence[src-1] = src-1
                                S = []
                                T = [(i+1) for i in range(len(self.matriceAdj))]
                        
                                while len(S) < len(self.matriceAdj):
                        
                                    # Choisir un sommet u qui n'est pas dans l'ensemble S et
                                    # qui a une valeur de distance minimale
                                    u = self.minDistance(dist, S, T)
                        
                                    # relaxation des sommets
                                    for v in range(len(self.matriceAdj)):
                                        if (self.matriceAdj[u][v] > 0) and (dist[v] > (dist[u] + self.matriceAdj[u][v])):
                                            dist[v] = dist[u] + self.matriceAdj[u][v]
                                            precedence[v] = u
                                self.Afficher(src, dist)
                        
                        
                        # Test
                        # les sommets sont numérotés à partir de 1
                        matriceAdj = [[0, 2, 4, 0, 0, 0],
                                      [0, 0, 1, 0, 7, 0],
                                      [0, 0, 0, 3, 0, 0],
                                      [0, 0, 0, 0, 2, 5],
                                      [0, 0, 0, 0, 0, 1],
                                      [0, 0, 0, 0, 0, 0],
                                      ]
                        g = Graphe(matriceAdj)
                        g.dijkstra(1)
                        
                
                        les chemins les plus courts allant de  1  est :
                        1 	 0
                        2 	 2
                        3 	 3
                        4 	 6
                        5 	 8
                        6 	 9   
                

Exemple :

L'ensemble S est initialement vide et les distances attribuées aux sommets sont {0, INF, INF, INF, INF, INF, INF},INF signifie infini.
Choisissez maintenant le sommet avec la valeur de distance minimale. Le sommet 1 est sélectionné, incluez-le dans S. Donc, S devient {1}.
Après avoir inclus dans S, mettez à jour les valeurs de distance de ses sommets adjacents. Les sommets adjacents de 1 sont et 3. Les valeurs de distance de 2 et 3 est 2 et 4 respectivement.
Après que le sous-graphe affiche les sommets et leurs valeurs de distance, seuls les sommets avec des valeurs de distance finies sont affichés. Les sommets inclus dans S sont affichés en couleur verte.

Sélectionnez le sommet avec la valeur de distance minimale et non déjà inclus dans S. Le sommet 2 est sélectionné et ajouté à S. Donc, S devient maintenant {1, 2}. Mettez à jour les valeurs de distance des sommets adjacents de 2. La valeur de distance de sommets {3, 5} devient {3, 9}.

Sélectionnez le sommet avec la valeur de distance minimale et non déjà inclus dans S. Le sommet 3 est sélectionné et ajouté à S. Donc, S devient maintenant {1, 2, 3}. Mettez à jour les valeurs de distance des sommets adjacents de 3. La valeur de distance du sommet 4 devient 6.

Nous répétons les étapes ci-dessus tant que S n'inclu pas tous les sommets d'un graphe donné. Enfin, nous obtenons l’arbre de chemin le plus court suivant.

Important ! L’algorithme de Dijkstra ne fonctionne pas pour les graphes avec des arêtes de poids négatives. L’algorithme de Bellman-Ford peut être utilisé pour les graphes avec des arêtes de poids négatives,

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :