Implémentation de la méthode Dyxtra par python

introduction

J'ai implémenté la méthode Dyxtra en python. Je n'ai pas l'habitude de poster, mais j'ai l'intention de l'écrire le plus clairement possible (mensonge)

Ayant récemment étudié la théorie des graphes à l'université, j'ai soudain voulu trouver le chemin le plus court lol Le code est sale, mais j'espère que cela aide quelqu'un!

Quelle est la méthode Dyxtra?

La méthode Dyxtra est un algorithme qui trouve le "chemin avec le plus petit poids". Voici quelques idées de base pour les algorithmes de Dyxtra:

1. Divisez le chemin avec le plus petit poids qui a été recherché pour les sommets en une partie confirmée et une partie indéterminée.
2. Mettez à jour l'itinéraire vers la partie incertaine en utilisant la valeur du côté entre la partie confirmée.
3. Augmentez les sommets du chemin avec le poids le plus petit qui a été déterminé séquentiellement un par un.
4. Effectuez les opérations ci-dessus jusqu'à ce que vous connaissiez les distances les plus courtes de tous les sommets.

Si vous ne savez pas de quoi vous parlez, je vous recommande de regarder la vidéo ci-dessous! Explication de l'algorithme Dyxtra de Yobinori

J'ai essayé de le faire

Je vais vous présenter le code tout de suite.

dijkstra.py

import heapq
class Map:  #Définir la classe de carte
    def __init__(self,start,goal):
        self.__start = start
        self.__goal = goal
        self.v_list =[] #[(0,s),(1,a)](poids,étiquette) 
        self.e_list = {}  #Dictionnaire secondaire
        self.dic_v_list = []
        self.dic_e_list ={}

    #Initialiser
    def add_list(self,cross_streets,load):
        for i in range(len(cross_streets)):
            if cross_streets[i]==self.__start:
                self.v_list.append((0,cross_streets[i]))
            else:
                self.v_list.append((float('inf'),cross_streets[i])) #float('inf')Est infini(∞,'a')
        
        if self.__start <= self.__goal:
            self.e_list = load
        else:
            #(1,2):S'il y a 5(2,1):Ajouter 5 au dictionnaire
            for ld in load:
                self.e_list.update({(ld[1],ld[0]):load[ld]})
    
    #Fonction pour ajouter un moyen
    def load_add(self,weight,label): 
        #Déterminez si c'est un début
        if weight != 0:
            #Trouvez le même chemin que l'étiquette ex. label:2→(1,2,4)
            loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k2 ==label]
            #Examiner tous les chemins qui contiennent l'étiquette spécifiée
            for load in loads:
                #Trouvez le sommet approprié et calculez le nouveau poids
                for (v0,v1) in [(v0,v1) for (v0,v1) in self.dic_v_list if v1==load[0]]:
                        #Déterminez si le poids de l'argument est égal au poids du chemin + du sommet
                        if weight == v0+load[2]:
                            self.dic_e_list.update([((load[0],load[1]),load[2])])

    #Suivez le chemin en sens inverse
    def back_calculation(self):
        #Objectif de remplacement
        label=[self.__goal]
        #Suivez le chemin du but au début
        while label[len(label)-1] != self.__start:
            load = [(k1,k2,val) for (k1,k2), val in self.dic_e_list.items() if k2 == label[len(label)-1]] #k est, par exemple, s,a,b
            label.append(load[0][0])
        return label

    def dijkstra(self):
        #Boucle jusqu'à ce qu'il n'y ait pas de sommets
        while len(self.v_list) > 0:
            #Trouvez le minimum
            heapq.heapify(self.v_list)
            (weight, label) = heapq.heappop(self.v_list)

            #Recherche d'une route adjacente
            loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k1 == label]

            for load in loads:
                #Trouver des poids correspondants dans une liste de paires
                for (v0,v1) in [(v0,v1) for (v0,v1) in self.v_list if v1==load[1]]:   
                        #Mettre à jour les poids
                        if weight + load[2] <= v0:
                            list_count = self.v_list.index((v0,v1)) #Remplacez le numéro d'élément de la liste
                            self.v_list[list_count] = (weight + load[2],v1)
            #Ajout de sommets et de chemins fixes
            self.dic_v_list.append((weight,label))
            self.load_add(weight,label)

    def serach(self):
        self.dijkstra()
        return self.back_calculation()

cross_streets = [1,2,3,4,5,6,7,8]  #Toutes les intersections(sommet)Liste de
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #Toutes les routes(Côté)dictionnaire
map = Map(7,1)  #Générer une instance de carte
map.add_list(cross_streets,load) #Faire une carte
print(map.serach())

Commentaire

* Seules les parties importantes seront expliquées.

v_list est une liste de type tuple d'étiquettes et de sommets, et e_list est un type de dictionnaire de côtés. (Par exemple, si la longueur du côté entre s-t est 10, elle est exprimée comme {(s, t): 10}) dic_v_list et dic_e_list stockent des sommets et des arêtes avec des distances de poids minimales fixes.

class Map:  #Définir la classe de carte
    def __init__(self,start,goal):
        self.__start = start
        self.__goal = goal
        self.v_list =[] #[(0,s),(1,a)](étiquette,sommet) 
        self.e_list = {}  #Dictionnaire secondaire
        self.dic_v_list = []
        self.dic_e_list ={}

Les sommets et les chemins sont passés comme suit:

cross_streets = [1,2,3,4,5,6,7,8]  #Toutes les intersections(sommet)Liste de
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #Toutes les routes(Côté)dictionnaire
map = Map(7,1)

La fonction la plus importante de ce programme est de trouver le chemin avec le moins de poids. Le flux est le suivant. ⑴ Utilisez heapq pour trouver le sommet avec le poids le plus petit. Puis retirez-le avec heapq.pop. ⑵ Stockez le côté s'étendant du sommet extrait en charge sous forme de type de liste. (3) Comparez les poids des sommets connectés pour chaque côté et mettez à jour si les poids peuvent être mis à jour. (4) Ajoutez les sommets et arêtes confirmés à dic_v_list et dic_e_list.

En d'autres termes, cette fonction est chargée de "trouver les sommets avec le moins de poids" et de "mettre à jour les poids des sommets adjacents".

    def dijkstra(self):
        #Boucle jusqu'à ce qu'il n'y ait pas de sommets
        while len(self.v_list) > 0:
            #Trouvez le minimum
            heapq.heapify(self.v_list)
            (weight, label) = heapq.heappop(self.v_list)

            #Recherche d'une route adjacente
            loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k1 == label]

            for load in loads:
                #Trouver des poids correspondants dans une liste de paires
                for (v0,v1) in [(v0,v1) for (v0,v1) in self.v_list if v1==load[1]]:   
                        #Mettre à jour les poids
                        if weight + load[2] <= v0:
                            list_count = self.v_list.index((v0,v1)) #Remplacez le numéro d'élément de la liste
                            self.v_list[list_count] = (weight + load[2],v1)
            #Ajout de sommets et de chemins fixes
            self.dic_v_list.append((weight,label))
            self.load_add(weight,label)

Le reste sont toutes des fonctions supplémentaires. (Omettre l'explication)

Résultat d'exécution

Essayez-le avec le graphique suivant.

Ils sont classés dans l'ordre du but au début, mais vous avez réussi à exécuter la réponse.

#données originales:Début 7,Objectif 1
cross_streets = [1,2,3,4,5,6,7,8]  #Toutes les intersections(sommet)Liste de
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #Toutes les routes(Côté)dictionnaire
map = Map(7,1)
#Résultat d'exécution
[1, 3, 5, 7]

#Bien sûr, il tient même s'il est inversé
cross_streets = [1,2,3,4,5,6,7,8]  #Toutes les intersections(sommet)Liste de
load = {(1,3):5,(1,2):1,(1,4):4,(2,4):2,(3,5):2,(4,5):5,(4,6):6,(5,8):1,(5,7):3,(6,7):2,(8,7):4} #Toutes les routes(Côté)dictionnaire
map = Map(1,7)
#Résultat d'exécution
[7, 5, 3, 1]