|
|
L’algoritmo di Pape-D’Esopo, per il calcolo dei cammini minimi, usa come insieme S una dequeue (double ended queue). Una dequeue è una coda che ammette anche l’inserzione in testa, e non solo in coda. Il generico nodo u verrà inserito la prima volta in coda ed in testa le volte successive. Più precisamente, se d[u] == MAXINT, allora u è inserito in coda, altrimenti in testa. L’idea dell’inserimento in testa è quella di sfruttare immediatamente il miglioramento dell’etichetta affinché esso si propaghi ai nodi vicini. L’algoritmo, nel caso pessimo, ha complessità superpolinomiale!! Tuttavia, si è sperimentalmente verificato essere uno dei più efficienti su grafi che modellano reti di comunicazione stradali, ovvero su grafi sparsi e planari. Un grafo è planare quando, disegnato su un piano, le linee corrispondenti a due archi istinti non si sovrappongono mai.
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.