Lezione 14.1: l'algoritmo dei cammini minimi successivi
Completion requirements
La necessaria teoria sull'algoritmo del cammini minimi successivi: statement dell'algoritmo, il caso vuoto. Il problema della correttezza: il cammino minimo può entrare in loop. La necessaria teoria: pseudoflussi minimali e loro caratterizzazione, come preservare la minimalità di uno pseudoflusso. Conseguenze: correttezza, terminazione e complessità dell'algoritmo dei cammini minimi successivi. Accenno a possibili miglioramenti: cammini minimi sui costi ridotti e loro uso per sfruttare le varianti veloci di SPT (SPT.S). Accenno all'applicazione: assegnamento di costo minimo, come diminuisce la complessità.