Vorrei chiedere se vi sembra giusto come ho risolto questo problema:
La sciatrice Lindsey Vonn ha inviato la sua assistente per misurare i dislivelli degli impianti di risalita e delle piste di una famosa località sciistica della Svizzera. L'assistente ritorna dopo diversi giorni di duro lavoro con una mappa di tutti gli impianti di risalita e di tutte le piste insieme al dislivello tra la stazione di partenza e la stazione di arrivo di ogni impianto e il dislivello tra la stazione di partenza e la stazione di arrivo di ogni pista. Una pista inizia dalla stazione di arrivo di un impianto di risalita e termina presso la stazione di partenza di un impianto di risalita potenzialmente diverso. Lindsey vuole verificare la mappa della sua assistente eseguendo il seguente controllo di integrità: partendo da un qualsiasi punto A, indipendentemente da come si scia (usando impianti di risalita e piste), il dislivello quando si torna ad A dovrebbe essere 0 (cioè, né strettamente negativo né strettamente positivo). Progetta un algoritmo per eseguire questo controllo di integrità e analizzarne il tempo di percorrenza in termini di numero di piste e impianti di risalita \( \left| E \right| \) e numero di stazioni di partenza e arrivo \( \left| V \right| \). Il tuo algoritmo dovrebbe essere eseguito in tempo polinomiale (in \( \left| E \right| \) ed \( \left| V \right| \) ).
Questo è quello che ho fatto:
Siccome la mappa è un grafo diretto con gli archi che sono pesati (con un peso positivo per gli impianti di risalita e negativo per le piste) usiamo Bellman-Ford per verificare la presenza di cicli negativi. Se c'è un ciclo negativo allora il controllo di integrità non passa altrimenti passa. Poi modifichiamo il grafo originale invertendo il segno dei pesi e applichiamo di nuovo Bellman-Ford per verificare la presenza di cicli negativi, in definitiva se in nessuno dei due casi è presente un ciclo negativo allora per qualsiasi \(A \in V \) abbiamo che qualunque ciclo che inizia e termina in \(A\) è di costo \(0\).
Quindi usiamo una volta Bellman-Ford che ha complessità \( O(\left| V \right| \left| E \right| ) \), poi modifichiamo i pesi \( w(e) \) per ogni \(e \in E \) in \(-w(e) \), facendo un loop for che ha \( \left| E \right| \) iterazioni, e per finire usiamo ancora Bellman-Ford con il nuovo grafo con i pesi aggiornati. Dunque con una complessità complessiva \( O(\left| V \right| \left| E \right| + \left| V \right| \left| E \right| + \left| E \right| ) = O( \left| V \right| \left| E \right|) \).