dijkstra's Algorithmus mit kürzestem Weg

Question

Kann mir jemand helfen oder mich in die richtige Richtung lenken Ich bin gerade verloren Ich weiß nicht, was sie bedeuten Werte in die Unendlichkeit setzen sie sprechen über die Kanten? oder ist das eine neue Variable, die jeder Knoten hat? Einige Ratschläge oder einige Hilfe, die in die richtige Richtung weisen, würden geschätzt werden. Heres, was ich habe bisher (obwohl seinen Müll meiner Meinung nach)

def dijkstra(self, start): 

    print("end dijkstra") 
    for node in self.__nodes: 
      curr_node = 0 
      for node in self.__nodes: 
       distances = float('inf') 
       before_node = None 

       print(node) 

    """ 
    try: 


     #for node in weighted_digraph: 
      #distances[node] = float('inf') 
      #predecessors[node] = None 
      print("work") 
      print(node) 
      #print(weighted_digraph) 
     #sp_set = [] 
     #distances[start] = 0 
    except TypeError: 
     print("BS OCCURED") 
    """ 

Answer 1

Also zunächst, Sie haben keine Ahnung, wie weit entfernt jeder Knoten von der Quelle (in der Tat, sie können alle überhaupt nicht erreichbar sein in der Fall, dass Ihr Graph nicht verbunden ist!). Dieses "auf Unendlichkeit setzen" -Geschäft hat mit der kürzest bekannten Entfernung vom Quellknoten zu jedem der Knoten zu tun. Jeder Ihrer Knoten muss wissen, wie weit er von der Quelle entfernt ist, und anfangs ist dieser Wert unendlich (weil Sie nicht entlang irgendwelcher Kanten gelaufen sind, um einen Pfad zu ihnen aufzuzählen).

Answer 2

Um Variablen Werte auf unendlich gesetzt, verwenden:

var = float('inf') 

Der Grund, warum dies in der Regel zu tun ist, wenn Sie das Minimum in einer Optimierungsfunktion finden wollen; Wenn Sie einen Wert auf unendlich setzen, können Sie ihn mit einem anderen Wert vergleichen und sicherstellen, dass der andere Wert niedriger ist.

In einem Maximierungsproblem Sie Werte auf minus unendlich zu Beginn wie folgt einstellen:

var = float('-inf') 

in Python> 3.5, CNA Sie auch das Mathematikmodul verwenden:

var = math.inf 
var = -math.inf 

Answer 3

Was bedeuten sie Werte bis unendlich, reden sie von den Rändern? auf alle anderen Knoten

Nein, reden sie über die Abstand eines Knotens, die Sie Dijkstra gehen auszuführen. Da du am Anfang die kürzeste Entfernung hast, lass es uns als unendlich bezeichnen. Hier

ist ein Beispiel dafür, wie Sie es initialisieren kann (in Pseudocode):

for each vertex v in Graph: 
    dist[v] ← INFINITY 
    prev[v] ← UNDEFINED // Previous node in optimal path from source 

dist[source] ← 0 //distance from a node to itself is zero.