Seltsames Verhalten von Dijkstras Algorithm in Python

Question

Ich versuche, Dijkstras Algorithm in Python zu implementieren. Ich möchte Länge von Knoten "You" zu allen anderen Knoten wissen.

def Dijkstr(): 
    listOfProcessingNodes = listOfNodes 
    for i in listOfNodes: 
     if i.name == "You": 
      i.lastNode = None 
      i.length = 0 
      i.resolved = True 
      lastProcessNode = i 

    listOfProcessingNodes.sort(key=lambda x: x.length, reverse=True) 

    while len(listOfProcessingNodes): 
     processNode = listOfProcessingNodes.pop() 
     for i in processNode.adjencyList: 
      for k in listOfEdges: 
       if (k.inNode == i.name and k.outNode == processNode.name and i.resolved == False) or (k.inNode == processNode.name and k.outNode == i.name and i.resolved == False): 
        i.length = processNode.length + int(float(k.cost)) 
        i.lastNode = processNode 
        i.resolved = True 
     listOfProcessingNodes.sort(key=lambda x: x.length, reverse=True) 
     lastProcessNode = processNode 
     print processNode.name,":", processNode.length 

Hier Definition von Klassen Node und Edge-:

class Node(): 
    def __init__(self, name): 
     self.name=name 
     self.adjencyList=[] 
     self.resolved = False 
     self.lastNode = None 
     self.length = float("inf") 

class Edge(): 
    def __init__(self, inNode, outNode, cost): 
     self.inNode=inNode 
     self.outNode=outNode 
     self.cost=cost 

für meine Eingabe

You - A: 3 
You - B: 2 
A - C: 4 
A - D: 4 
B - D: 1 
B - E: 2 
C - F: 1 
D - F: 2 
D - G: 4 
E - G: 2 
F - G: 2 

ich diese Ausgabe erhalten

You : 0 
B : 2 
A : 3 
D : 3 
E : 4 
F : 5 
C : 7 
G : 7 

Statt

You : 0 
B : 2 
A : 3 
D : 3 
E : 4 
F : 5 
C : 6 
G : 6 

Ich bin wirklich verwirrt, wenn es nicht für alle Knoten funktioniert, so mache ich eine Fehlentscheidung, aber wenn es nicht für die letzten 2 Knoten funktioniert? Danke für Ihre Hilfe

Answer 1

Es scheint, dass Sie einen entscheidenden Teil des Dijkstra-Algorithmus falsch verstanden haben. Wenn der Algorithmus fortschreitet, ist es möglich, dass die "Länge" eines Knotens (dh die minimalen Gesamtkosten von dem "Du" -Knoten) abnimmt, wenn der Algorithmus eine Route zu diesem Knoten findet, die "billiger" ist "als man zuvor gefunden hat. Ihr Code geht davon aus, dass nach dem einmaligen Besuch eines Knotens dessen Länge festgelegt wird. Das ist falsch.

Ihr Diagramm enthält eine solche Situation, in der dies geschieht. Wenn Sie den Knoten D mit der Länge 3 besuchen, geben Sie F eine Länge von 5 und G eine Länge von 7 an. Wenn Sie jedoch den Knoten E mit der Länge 4 besuchen, müssen Sie die Länge von G auf 6 reduzieren, da E Länge hat 4 und die Kante von E bis G hat 2.

Statt Ausfiltern beliebigen Knoten kosten wo resolved zu True gesetzt ist, zu überprüfen, ob die Länge der processNode zuzüglich der Kosten der Kante als die aktuelle weniger k ist zu sehen bekannte Länge des Knotens i. Wenn dies der Fall ist, haben Sie eine neue niedrigere Länge für den Knoten i gefunden. Daher sollten Sie die Länge des Knotens i und seines vorherigen Knotens aktualisieren.

Übrigens sollte die Länge von Knoten C 7 sein, nicht 6, wie Sie behaupten.