Lezione 8.2: SPT.L.Queue in teoria e le varianti che portano a SPT.S
Aggregazione dei criteri
Analisi teorica dell'algoritmo SPT. Il caso del ciclo negativo. Completezze e terminazione, complessità computazionale dipendente dalla scelta di Q. La versione "naturale": algoritmo di Bellman SPT.L, sue proprietà ed accenno di dimostrazione (le fasi, la proprietà delle etichette), complessità computazionale ed utilizzo per determinare l'esistenza di cicli negativi. Varianti dell'algoritmo SPT.L: deque, 2-queue. Accenno agli algoritmi threshold. Evoluzione "naturale": algoritmo SPT.S. Esecuzione di SPT.S, vedere in pratica le proprietà principali (ciascun nodo esce una sola volta, valori delle etichette).