|
|
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 di priorità realizzata come una lista non ordinata, si ottiene l’algoritmo di Dijkstra (1959). Gli elementi di S sono i nodi u con priorità data dal valore du. Ad ogni iterazione estraggo da S il nodo di etichetta minima con gli operatori min e cancellamin. Se vale che cuv >= 0 (l’ arco non ha lunghezza negativa), allora l’algoritmo ha complessità polinomiale in quanto ogni nodo viene estratto da S una ed una sola volta. Il ciclo while viene eseguito n volte e all’interno del ciclo, le operazioni più costose sono min e cancellamin che risultano O(n). In conclusione, Dijkstra ha complessità O(n2).
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.