Lezione 9.1: ultimi fuochi sui cammini minimi
Completion requirements
Ultimi fuochi sui cammini minimi: proprietà di SPT.S, (nel caso di costi non negativi), conseguenze (terminazione "veloce" con una o poche destinazioni), cammino minimo con insieme di sorgenti. Grafi aciclici, buona numerazione e come calcolarla, algoritmo SPT.Acyclic e sue buone proprietà (complessità lineare, risolve sempre il cammino minimo e quello massimo).