Почему мы выполняем топологическую сортировку, чтобы найти кратчайший или самый длинный путь во взвешенном DAG?
-
29-09-2020 - |
Вопрос
Мне было интересно, зачем нам нужно выполнять топологическую сортировку перед выполнением расслабления ребер.
Не лучше ли было бы, если бы мы это сделали :если начальная вершина равна "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[]
Решение
При использовании этого алгоритма ожидаемая временная сложность не была бы 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
) и их уже посетили.