Por que fazemos classificação topológica para encontrar o caminho mais curto ou mais longo no DAG ponderado?

Question

Eu queria saber por que precisamos fazer a classificação topológica antes de realizar o relaxamento das arestas.

Não seria melhor se fizéssemos:se o vértice inicial for "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

Eu deixei intencionalmente de fora o array visitado[]

Answer 1

Ao usar este algoritmo, a complexidade de tempo esperada não seria O(V+E) já que temos que visitar uma borda várias vezes.

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

Mas usando a classificação topológica, obtemos a ordem em que os vértices devem ser percorridos para que uma aresta seja visitada exatamente uma vez.Então poderíamos ter garantido T.C.de O(V+E).

Então, para resolver esse problema para trabalhar em O(V+E) usamos classificação topológica.

Mas acho que isso não basta, devemos saber também porque usar a ordenação Topológica aqui e para que ela ajude em outros problemas.

Por que ordenação topológica?

A ordenação topológica nos dá a ordem como 0 1 2 3 4 5 então, quando chegarmos a um nó nesta ordem (digamos 4) então já calculamos o caminho mais curto para ele (4) como todas as arestas (bem como caminhos) do tipo u -> v (v = 4) e já foram visitados.