Implementierung der Dyxtra-Methode durch Python
Einführung
Ich habe die Dyxtra-Methode in Python implementiert. Ich bin es nicht gewohnt zu posten, aber ich beabsichtige es so klar wie möglich zu schreiben (Lüge)
Nachdem ich kürzlich an der Universität Graphentheorie studiert hatte, wollte ich plötzlich den kürzesten Weg finden lol Der Code ist schmutzig, aber ich hoffe, er hilft jemandem!
Was ist die Dyxtra-Methode?
Die Dyxtra-Methode ist ein Algorithmus, der den "Pfad mit dem kleinsten Gewicht" findet. Hier sind einige grundlegende Ideen für Dyxtras Algorithmen:
- Teilen Sie den Pfad mit dem kleinsten Gewicht, das nach den Eckpunkten gesucht wurde, in einen bestätigten Teil und einen unbestimmten Teil.
- Aktualisieren Sie die Route zum unsicheren Teil anhand des Werts der Seite zwischen dem bestätigten Teil.
- Erhöhen Sie die Eckpunkte des Pfades mit dem kleinsten Gewicht, das nacheinander nacheinander bestimmt wurde.
- Führen Sie die obigen Vorgänge aus, bis Sie die kürzesten Abstände aller Scheitelpunkte kennen.
Wenn Sie nicht wissen, wovon Sie sprechen, empfehle ich Ihnen, das folgende Video anzusehen! Erklärung des Dyobra-Algorithmus von Yobinori
Versuchte es zu schaffen
Ich werde den Code sofort einführen.
dijkstra.py
import heapq
class Map: #Kartenklasse definieren
def __init__(self,start,goal):
self.__start = start
self.__goal = goal
self.v_list =[] #[(0,s),(1,a)](Gewicht,Etikette)
self.e_list = {} #Seitenwörterbuch
self.dic_v_list = []
self.dic_e_list ={}
#Initialisieren
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')Ist unendlich(∞,'a')
if self.__start <= self.__goal:
self.e_list = load
else:
#(1,2):Wenn es 5 gibt(2,1):Fügen Sie dem Wörterbuch 5 hinzu
for ld in load:
self.e_list.update({(ld[1],ld[0]):load[ld]})
#Funktion, um einen Weg hinzuzufügen
def load_add(self,weight,label):
#Bestimmen Sie, ob es ein Anfang ist
if weight != 0:
#Suchen Sie den gleichen Pfad wie das Etikett ex. label:2→(1,2,4)
loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k2 ==label]
#Untersuchen Sie alle Pfade, die die angegebene Bezeichnung enthalten
for load in loads:
#Finden Sie den geeigneten Scheitelpunkt und berechnen Sie das neue Gewicht
for (v0,v1) in [(v0,v1) for (v0,v1) in self.dic_v_list if v1==load[0]]:
#Bestimmen Sie, ob das Argumentgewicht gleich dem Pfad + Scheitelpunktgewicht ist
if weight == v0+load[2]:
self.dic_e_list.update([((load[0],load[1]),load[2])])
#Folgen Sie dem Pfad in umgekehrter Richtung
def back_calculation(self):
#Ersatzziel
label=[self.__goal]
#Folgen Sie dem Weg vom Ziel zum Start
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 ist zum Beispiel s,a,b
label.append(load[0][0])
return label
def dijkstra(self):
#Schleife, bis keine Eckpunkte mehr vorhanden sind
while len(self.v_list) > 0:
#Finde das Minimum
heapq.heapify(self.v_list)
(weight, label) = heapq.heappop(self.v_list)
#Ich suche eine angrenzende Straße
loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k1 == label]
for load in loads:
#Finden Sie passende Gewichte in einer Liste von Paaren
for (v0,v1) in [(v0,v1) for (v0,v1) in self.v_list if v1==load[1]]:
#Gewichte aktualisieren
if weight + load[2] <= v0:
list_count = self.v_list.index((v0,v1)) #Ersetzen Sie die Elementnummer der Liste
self.v_list[list_count] = (weight + load[2],v1)
#Feste Eckpunkte und Pfade hinzugefügt
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] #Alle Kreuzungen(Scheitel)Liste von
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} #Alle Straßen(Seite)Wörterbuch
map = Map(7,1) #Karteninstanz generieren
map.add_list(cross_streets,load) #Mach eine Karte
print(map.serach())
Kommentar
* Es werden nur wichtige Teile erklärt.
v_list ist eine Tupelliste mit Beschriftungen und Scheitelpunkten, und e_list ist ein Wörterbuchtyp mit Seiten. (Wenn beispielsweise die Länge der Seite zwischen s-t 10 beträgt, wird dies als {(s, t): 10} ausgedrückt.) dic_v_list und dic_e_list speichern Eckpunkte und Kanten mit festen Mindestgewichtsabständen.
class Map: #Kartenklasse definieren
def __init__(self,start,goal):
self.__start = start
self.__goal = goal
self.v_list =[] #[(0,s),(1,a)](Etikette,Scheitel)
self.e_list = {} #Seitenwörterbuch
self.dic_v_list = []
self.dic_e_list ={}
Die Eckpunkte und Pfade werden wie folgt übergeben:
cross_streets = [1,2,3,4,5,6,7,8] #Alle Kreuzungen(Scheitel)Liste von
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} #Alle Straßen(Seite)Wörterbuch
map = Map(7,1)
Die wichtigste Funktion in diesem Programm, um den Pfad mit dem geringsten Gewicht zu finden. Der Fluss ist wie folgt. ⑴ Verwenden Sie heapq, um den Scheitelpunkt mit dem geringsten Gewicht zu finden. Dann nehmen Sie es mit heapq.pop heraus. ⑵ Speichern Sie die vom extrahierten Scheitelpunkt ausgehende Seite beim Laden als Listentyp. (3) Vergleichen Sie die Gewichte der verbundenen Eckpunkte für jede Seite und aktualisieren Sie, ob die Gewichte aktualisiert werden können. (4) Fügen Sie die bestätigten Eckpunkte und Kanten zu dic_v_list und dic_e_list hinzu.
Mit anderen Worten, diese Funktion ist dafür verantwortlich, "die Scheitelpunkte mit dem geringsten Gewicht zu finden" und "die Gewichte benachbarter Scheitelpunkte zu aktualisieren".
def dijkstra(self):
#Schleife, bis keine Eckpunkte mehr vorhanden sind
while len(self.v_list) > 0:
#Finde das Minimum
heapq.heapify(self.v_list)
(weight, label) = heapq.heappop(self.v_list)
#Ich suche eine angrenzende Straße
loads = [(k1,k2,val) for (k1,k2), val in self.e_list.items() if k1 == label]
for load in loads:
#Finden Sie passende Gewichte in einer Liste von Paaren
for (v0,v1) in [(v0,v1) for (v0,v1) in self.v_list if v1==load[1]]:
#Gewichte aktualisieren
if weight + load[2] <= v0:
list_count = self.v_list.index((v0,v1)) #Ersetzen Sie die Elementnummer der Liste
self.v_list[list_count] = (weight + load[2],v1)
#Feste Eckpunkte und Pfade hinzugefügt
self.dic_v_list.append((weight,label))
self.load_add(weight,label)
Der Rest sind alle zusätzlichen Funktionen. (Erklärung weglassen)
Ausführungsergebnis
Versuchen Sie es mit der folgenden Grafik.
Sie sind in der Reihenfolge vom Ziel bis zum Start angeordnet, aber Sie haben die Antwort erfolgreich ausgeführt.
#Originale Daten:Starten Sie 7,Ziel 1
cross_streets = [1,2,3,4,5,6,7,8] #Alle Kreuzungen(Scheitel)Liste von
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} #Alle Straßen(Seite)Wörterbuch
map = Map(7,1)
#Ausführungsergebnis
[1, 3, 5, 7]
#Natürlich gilt es auch, wenn es umgekehrt ist
cross_streets = [1,2,3,4,5,6,7,8] #Alle Kreuzungen(Scheitel)Liste von
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} #Alle Straßen(Seite)Wörterbuch
map = Map(1,7)
#Ausführungsergebnis
[7, 5, 3, 1]
Recommended Posts