[Teoria] Bellman-Ford e cicli negativi.

[3m0o]

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|) \).

[apatriarca]

Non sono sicuro sia sufficiente far girare Bellman-Ford due volte in quel modo. Più che altro perché non mi sembra si dica che il grafo è necessariamente connesso.

[3m0o]

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.

Il fatto è che dev'essere connesso altrimenti non avrebbe senso. Se un impianto di risalita mi porta in un luogo senza pista di scii rimango bloccato lì in cima alla montagna. E mi dice nel problema che una pista termina presso la stazione di partenza di un impianto di risalita (non necessariamente lo stesso che mi ha portato al inizio della pista).

[apatriarca]

Se fosse un vero impianto sciistico probabilmente sarebbe connesso - ma potrebbero esserci strade invece di impianti di risalita o piste per connettere alcune delle stazioni. Tuttavia le tue condizioni non sono sufficienti perché il grafo sia connesso. Un esempio:

Stazioni di risalita: A e B
Stazioni di discesa: C e D
Puoi andare da A a C e viceversa.
Puoi andare da B a D e viceversa.

Il grafo è disconnesso eppure ad ogni stazione di discesa c'è almeno una pista e ad ogni stazione di salita c'è almeno un impianto di risalita. La tua soluzione comunque può funzionare anche in questo caso a patto di far girare l'algoritmo più volte (due per ogni parte connessa). In alternativa puoi usare qualcosa come Floyd-Warshall.