Compute Pfade - Dijkstra-Algorithmus

Question

ich eine Implementierung von Dijkstra-Algorithmus zu sehen, und ich habe nicht ganz verstanden, einige Teile dieses Codes:

public static void computePaths(Vertex source) { 
    source.minDistance = 0; 
    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); 
    vertexQueue.add(source); 

    while (!vertexQueue.isEmpty()) { 
     Vertex u = vertexQueue.poll(); 

     // Visit each edge exiting u 
     for (Edge e : u.adjacencies) { 
      Vertex v = e.target; 
      double distanceThroughU = u.minDistance + e.getweight(); 
      if (distanceThroughU < v.minDistance) { 
       vertexQueue.remove(v);  //How can I remove if I didn't add it first, and why do I need to remove? 
       v.minDistance = distanceThroughU; 
       v.previous = u; 
       vertexQueue.add(v);  //Why is it add again? 
      } 
     } 
    } 
} 

ich über Dijkstra-Algorithmus gelesen, damit ich die allgemeine Logik weiß aber, während ich Als ich diese Implementierung sah, gab es ein paar Dinge, die ich nicht verstand, warum sie gemacht wurden. Kann jemand bitte versuchen zu erklären? Vor allem, wo ich die Kommentare habe!

Answer 1

Um die Informationen des Knotens v aktualisieren

Sie wollen die Informationen des Knotens v aktualisieren, weil Sie einen kürzeren in der Prioritätswarteschlange gespeichert Weg zu ihm gefunden.

Die Funktion Remove() entfernt den Knoten , wenn in der Prioritätswarteschlange vorhanden ist.

Danach aktualisieren Sie die Informationen und fügen sie dann erneut mit den aktualisierten Informationen hinzu.