Pagina Radice del Progetto: Cammini minimi in grafi non orientati e conservativi
Dato un grafo non orientato G=(V,E),
ed un assegnamento w di pesi possibilmente negativi
agli archi di G,
la coppia (G,w) vien detta conservativa se non esistono
cicli di peso totale negativo.
Vorremmo codificare in noweb e c++ un algoritmo
che computi le distanze in una coppia (G,w) conservativa.
L'algoritmo termina con i cammini ottimi o dimostando
la non conservatività di (G,w) tramite l'esibizione
di un ciclo negativo.
Come riferimento, potete attenervi al seguente
lavoro qui disponibile in formato .ps:
Conforti, Michele; Rizzi, Romeo
Shortest paths in conservative graphs.
Discrete Math. 226 (2001), no. 1-3, 143--153.