Dijkstra-Algorithmus mit Min-Priority-Warteschlange

Question

Ich versuche, den Dijkstra-Algorithmus mit der Prioritätswarteschlange zu implementieren, aber ich kann nicht verstehen, wie es funktioniert. Ich lese viele Führer im Web, aber ich kann diesen Algorithmus überhaupt nicht verstehen.

Meine Frage ist: Was ist die Priorität für jeden Knoten? Ich denke, dass es das Gewicht der ankommenden Kante mit minimalem Wert ist, aber ich bin mir nicht sicher. Ist das wahr?

Zweite Frage, wenn ich die Wurzel der Warteschlange extrahieren, wie funktioniert, wenn dieser Knoten keine Nachbarschaft mit keinem der besuchten Knoten ist?

Answer 1

Sie sollten priority queue verwenden, wobei die vertex mit der kürzesten Entfernung vom Start vertex die höchste Priorität erhält. Zunächst müssen alle vertices den kürzesten Abstand der Unendlichkeit und die vertex Start wird durch das Einfügen aller vertices (mit seinem edges) aus der grafischen Darstellung innerhalb der PQ den kürzesten Abstandes 0.

beginnen. Entfernen Sie vertex aus dem PQ und erkunden Sie alle edges. Vergleichen Sie die kürzesten Entfernungen mit allen benachbarten vertices und wenn der Abstand kleiner ist als der kürzeste Abstand auf dem aktuellen vertex, aktualisieren Sie die nächstliegende vertex kürzeste Strecke innerhalb der PQ. Fortfahren, während PQ nicht leer ist. Vertices, die keine edges bekommen, wird mit der kürzesten Entfernung von Unendlichkeit enden, weil es nicht möglich ist, zu ihnen vom Anfang vertex zu kommen. Sie werden jedoch immer noch aus der PQ entfernt.

Pseudocode

initialize graph 
initialize pq 
pq.insertAll(graph.getVertices()) 

while (pq is not empty) { 
    vertex = pq.remove() 
    edges = vertex.getEdges() 

    for all edges { 
    destination = edge.getDestination() 
    newDistance = edge.getLength() + vertex.getDistance() 
    if (newDistance < destination.getDistance()) { 
     destination.setShortestDistance(newDistance) 
     pq.update(destination) 
    } 
    } 
} 

MIT Opencourseware Links:
Path problems overview
Dijkstra