[Teoria] Ordinamento topologico

[3m0o]

Nel seguente esercizio non capisco perché dobbiamo ordinare topologicamente i vertici...


Sei in piedi sulla cima della montagna. Dato che la salita è stata piuttosto dura, vuoi pianificare attentamente la tua sciata in modo da massimizzare la tua esperienza. Per aiutarti hai una mappa con tutti i punti di vista eccellenti pesati in base alla loro bellezza: più alto è il numero, migliore è la vista.
La tua posizione di partenza è etichettata s e devi terminare la tua discesa a t dove hai parcheggiato la macchina. Questo significa che potresti non riuscire a visitare tutti i punti di vista.

Input: un grafo aciclico diretto \(G=(V,E) \) con vertici pesati \(w : V \to \mathbb{R} \),, una fonte \(s \in V \) e un lavandino \(t \in V \).

Output: Il peso massimo di un percorso da \(s\) a \(t\), dove il peso di un percorso è la somma dei pesi dei suoi vertici.

Il tuo compito è quello di progettare e analizzare un algoritmo per il problema che runna in tempo \( O(\left| V \right| + \left| E \right| ) \).

Le soluzioni dicono questo:
Come primo step trasformiamo il nostro grafo con pesi sui vertici in un grafo con archi pesati, per fare questo definiamo \( w_1 : E \to \mathbb{R} \) tale che \( w_1(s,v)=w(s)+w(v) \) e \( w_1(u,v)=w(v) \) se \(u \neq s \). Sia \(m(u) \) il peso massimo di un percorso che inizia in \(s\) e termina in \(u\). Chiaramente \(m(s)=0\). Abbiamo la seguente formula ricorsiva
\[ m(u)= \max_{(v,u) \in E}\{ m(v) + w_1(v,u) \}, u \neq s \]
Per calcolare efficientemente \(m(u) \) dobbiamo aver già calcolato \(m(v) \) per ogni vertice con archi che arrivano in \(u\). A tal fine continuiamo ordinando topologicamente i vertici. Per fare ciò associamo ad ogni vertice un numero da \(1\) ad \(n\) che descrive la posizione del vertice in ordine topologico. Per rendere la descrizione più semplice diciamo che \(p : \{1,\ldots,n\} \to V \) è la funzione che descrive la posizione dei vertici. Infine usiamo l'approccio bottom up per calcolare \(m(t)\). Notando che l'ordinamento topologico può essere eseguito in tempo lineare \( O(\left| V \right| + \left| E \right| ) \) e che il loop della programmazione dinamica usa al massimo \( \left| E \right| \) comparazioni otteniamo in totale una complessità di esecuzione uguale a \( O(\left| V \right| + \left| E \right| ) \).

[Quinzio]

Al di la del formalismo matematico, per fare quello che chiede l'esercizio, devi partire dal verice source e poi percorrere il grafo in modo depth first, sommando i pesi degli edges mentre li percorri, fino al vertice sink (lavandino ).
Ad ogni vertice, che inizialmente ha associato un valore 0, se lo attraversi con una somma maggiore al valore associato al vertice, la somma diventa il nuovo valore del vertice (realizzando la funzione $max$).
Per fare tutto questo (in un tempo lineare), devi avere i vertici ordinati in modo topologico (https://it.wikipedia.org/wiki/Ordinamento_topologico).

[apatriarca]

L'ordinamento topologico garantisce che quando calcoli il valore $m(u)$, tutti i valori $m(v)$ per cui $v \to u \in E$ sono effettivamente già stati calcolati. Un ordinamento topologico è infatti tale se ha la proprietà per cui se $v \to u \in E$ allora $v$ deve venire prima di $u$ nell'ordinamento.

[3m0o]

Capito grazie