Perché facciamo ordinamento topologico per trovare il percorso più breve o più lungo nel dag ponderato?
-
29-09-2020 - |
Domanda
Mi stavo chiedendo perché dobbiamo fare il tipo topologico prima di eseguire rilassamento dei bordi.
Non sarebbe meglio se lo facciamo: Se l'avvio vertice è "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
.
Avevo intenzionalmente escluso la [] array <] array
Soluzione
Utilizzando questo algoritmo la complessità del tempo prevista non sarebbe generatoDicetagcode poiché dobbiamo visitare un vantaggio più volte.
O(V+E)
Ma usando l'ordinamento topologico, otteniamo l'ordine in cui i vertici dovrebbero essere attraversati in modo che un bordo sia visitato esattamente una volta.Quindi potremmo aver garantito T.C.di 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
.
Quindi per risolvere questo problema per lavorare in O(V+E)
usiamo il tipo topologico.
Ma penso che questo non sia abbastanza, dovremmo anche sapere perché usare l'ordinazione topologica qui e così che aiuta in altri problemi.
Perché ordinamento topologico?
Ordinamento topologico ci dà l'ordine come O(V+E)
, una volta raggiunto un nodo in questo ordinamento (diciamo 0 1 2 3 4 5
) Allora abbiamo già calcolato il percorso più breve ad esso (4
) come tutti i bordi (così come percorsi)di tipo 4
(u -> v
) e sono già stati visitati.