Почему мы выполняем топологическую сортировку, чтобы найти кратчайший или самый длинный путь во взвешенном DAG?

Question

Мне было интересно, зачем нам нужно выполнять топологическую сортировку перед выполнением расслабления ребер.

Не лучше ли было бы, если бы мы это сделали :если начальная вершина равна "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

Я намеренно пропустил массив visited[]

Answer 1

При использовании этого алгоритма ожидаемая временная сложность не была бы O(V+E) поскольку нам приходится посещать край несколько раз.

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

Но, используя топологическую сортировку, мы получаем порядок, в котором должны быть пройдены вершины, чтобы ребро было посещено ровно один раз.Так что мы могли бы гарантировать T.C.из O(V+E).

Итак, чтобы решить эту проблему, нужно работать в O(V+E) мы используем топологическую сортировку.

Но я думаю, этого недостаточно, мы также должны знать, зачем использовать здесь топологическое упорядочение и чтобы это помогло в других проблемах.

Почему именно топологическое упорядочение ?

Топологическое упорядочение дает нам такой порядок, как 0 1 2 3 4 5 затем, как только мы достигнем узла в этом порядке (скажем 4) тогда мы уже вычислили кратчайший путь к нему (4) как все ребра (а также контуры) типа u -> v (v = 4) и их уже посетили.