¿Por qué hacemos la clasificación topológica para encontrar la ruta más corta o más larga en DAG ponderado?

Question

Me preguntaba por qué necesitamos hacer el tipo topológico antes de realizar la relajación de los bordes.

no sería mejor si lo hacemos: Si iniciar el vértice es "S"

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

He dejado fuera intencionalmente visitado [] Array

Answer 1

Al usar este algoritmo, la complejidad de tiempo esperada no sería O(V+E), ya que tenemos que visitar un borde varias veces.

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

Pero al usar la clasificación topológica, obtenemos el orden en que se deben recorrer los vértices para que se visite un borde exactamente una vez.Así que podríamos haber garantizado T.C.de O(V+E).

Para resolver este problema para trabajar en O(V+E), usamos un tipo topológico.

Pero creo que esto no es suficiente, también deberíamos saber por qué usar pedidos topológicos aquí y para que ayude en otros problemas.

¿Por qué pedido topológico?

El pedido topológico nos da la orden como 0 1 2 3 4 5 entonces, una vez que lleguemos a un nodo en este orden (digamos 4), ya hemos calculado la ruta más corta (4) como todos los bordes (así como las rutas)de tipo u -> v (v = 4) y ya se han visitado.