Dijkstra-Algorithmus mit topologische Sortierung

Question

ich auf diese Stelle in einem Lehrbuch kam.

„Wenn der Graph azyklisch ist, können wir Dijkstra-Algorithmus verbessern Vertices da in topologischer Reihenfolge ausgewählt werden können, wenn ein Scheitelpunkt ausgewählt wird, dessen Abstand kann nicht mehr gesenkt werden, weil von unbekannten Knoten keine Kanten kommen. "

Ich verstehe Topologische Sort und Dijkstra-Algorithmus, aber verstehe nicht, wie topologische Reihenfolge Dijkstra's beschleunigen kann, insbesondere wenn die Reihenfolge nicht immer eindeutig ist. (außer es bezieht sich auf Raumkomplexität, die auch keinen Sinn macht)

Kann jemand erklären, wie es es verbessert und ein Beispiel gibt?

Answer 1

Sie können eine beliebige topologische Sortierung auswählen und die Scheitelpunkte in dieser Reihenfolge bearbeiten.

Die zeitliche Komplexität ist in der Größe des Graphen linear, da keine Prioritätswarteschlange mehr benötigt wird. Sie können einfach alle Scheitelpunkte in topologischer Reihenfolge durchlaufen und die Entfernung für sie berechnen.

Es geht so:

dist = 0 for the start vertex and +inf for the rest 
for v in topological order: 
    for u in neighbors[v] in reverse graph: 
     dist[v] = min(dist[v], dist[u] + weight(u, v))  

Die Richtigkeit folgt aus der Tatsache, dass durch die Zeit, die wir v erreichen, haben wir bereits alle Knoten verarbeitet, um eine Kante zu v (durch die Definition eines topologischen haben Auftrag).