Pourquoi effectuons-nous un tri topologique pour trouver le chemin le plus court ou le plus long dans un DAG pondéré ?

Question

Je me demandais pourquoi devons-nous faire le tri topologique avant d'effectuer le relâchement des bords.

Ne serait-il pas préférable de faire :si le sommet de départ est "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

J'avais intentionnellement laissé de côté le tableau visité[]

Answer 1

En utilisant cet algorithme, la complexité temporelle attendue ne serait pas O(V+E) car nous devons visiter un bord plusieurs fois.

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

Mais en utilisant le tri topologique, nous obtenons l’ordre dans lequel les sommets doivent être parcourus pour qu’une arête soit visitée exactement une fois.Nous aurions donc pu garantir à T.C.de O(V+E).

Donc, pour résoudre ce problème, travailler O(V+E) nous utilisons le tri topologique.

Mais je pense que cela ne suffit pas, nous devrions aussi savoir pourquoi utiliser l'ordre topologique ici et pour qu'il aide dans d'autres problèmes.

Pourquoi un ordre topologique ?

L'ordre topologique nous donne l'ordre comme 0 1 2 3 4 5 puis, une fois que nous atteignons un nœud dans cet ordre (disons 4) alors nous avons déjà calculé le chemin le plus court pour y accéder (4) ainsi que toutes les arêtes (ainsi que les chemins) de type u -> v (v = 4) et ont déjà été visités.