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.


[Back] created:   30 Aprile 2001
updated:   30 Aprile 2001
© Dipartimento di Matematica
University of Verona