|
|
Nel calcolo dei cammini minimi per ottenere una procedura efficiente, non basta che la struttura dati S utilizza sia un generico “insieme” con un’ altrettanto generica operazione “leggi”, ma occorre specificarle ulteriormente (vedi funzione SPT scritta in linguaggio C).
Se l’insieme S è una coda, si ottiene un algoritmo di complessità polinomiale anche nel caso in cui cuv <= 0. La struttura dell’algoritmo è quella di una visita BFS in cui la marcatura del nodo u consiste nel diminuire l’etichetta du. Ogni nodo quindi può essere estratto dalla coda S al più n-1 volte. La complessità dell’algoritmo è O( nm ), dove m è il numero degli archi. Se l’insieme S è una pila, la complessità dell’algoritmo diventa superpolinomiale. Infatti, si può mostrare che ogni nodo può essere inserito nella pila un numero di volte esponenziale!!!
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.