Warum führen wir eine topologische Sortierung durch, um den kürzesten oder längsten Pfad im gewichteten DAG zu finden?

Question

Ich habe mich gefragt, warum wir die topologische Sortierung durchführen müssen, bevor wir die Kanten entspannen.

Wäre es nicht besser, wenn wir Folgendes tun würden:wenn der Startscheitelpunkt „s“ ist

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

Ich habe absichtlich das besuchte[]-Array weggelassen

Answer 1

Durch die Verwendung dieses Algorithmus wäre die erwartete Zeitkomplexität nicht höher O(V+E) da wir eine Kante mehrmals besuchen müssen.

queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue

Aber durch die topologische Sortierung erhalten wir die Reihenfolge, in der die Eckpunkte durchlaufen werden sollen, damit eine Kante genau einmal besucht wird.Wir hätten also T.C. garantieren können.von O(V+E).

Um dieses Problem zu lösen, müssen wir daran arbeiten O(V+E) Wir verwenden die topologische Sortierung.

Aber ich denke, das reicht nicht aus, wir sollten auch wissen, warum wir hier die topologische Reihenfolge verwenden und damit sie bei anderen Problemen hilft.

Warum topologische Ordnung?

Die topologische Ordnung gibt uns die Ordnung wie 0 1 2 3 4 5 Sobald wir dann einen Knoten in dieser Reihenfolge erreichen (sagen wir 4), dann haben wir bereits den kürzesten Weg dorthin berechnet (4) wie alle Kanten (sowie Pfade) des Typs u -> v (v = 4) und wurden bereits besucht.