|
==Pseudocodice==
Nel seguente algoritmo, il codice <code>u := vertici in ''Q'' con la più breve dist[]</code>, cerca per dei vertici <code><var>u</var></code> nell'insieme dei vertici <code><var>Q</var></code> che hanno il valore <code>dist[<var>u</var>]</code> più piccolo. Questi vertici sono rimossi dall'insieme <code><var>Q</var></code> e restituiti all'utente. <code>dist_between(<var>u</var>, <var>v</var>)</code> calcola la distanza tra due nodi vicini <code><var>u</var></code> e <code><var>v</var></code>. La variabile <code><var>alt</var></code> nelle linee 20 22 rappresenta la lunghezza del percorso dal nodo iniziale al nodo vicino <code><var>v</var></code> se passa da <code><var>u</var></code>. Se questo percorso è più corto dell'ultimo percorso registrato per <code><var>v</var></code>, allora il percorso corrente è rimpiazzato dal percorso identificato con <code><var>alt</var></code>. L'array <code>precedente</code> è popolato con un puntatore al nodo successivo del grafo sorgente per ricevere il percorso più breve dalla sorgente.
P
1 '''function''' Dijkstra(''Grafo'', ''sorgente''):
2 '''For each''' vertice ''v'' in ''Grafo'': ''// Inizializzazione''
3 dist[''v''] := infinito ; ''// Distanza iniziale sconosciuta''
4 ''// dalla sorgente a v''
5 precedente[''v''] := non definita ; ''// Nodo precedente in un percorso ottimale
6 '''end for''' ''// dalla sorgente''
7
8 dist[''sorgente''] := 0 ; ''// Distanza dalla sorgente alla sorgente''
9 ''Q'' := L'insieme di tutti i nodi nel ''Grafo'' ; ''// Tutti i nodi nel grafo sono''
10 ''// Non ottimizzati e quindi stanno in Q''
11 '''while''' ''Q'' '''non è''' vuota: ''// Loop principale''
12 ''u'' := vertice in ''Q'' con la più breve distanza in dist[] ; ''// Nodo iniziale per il primo caso''
13 rimuovi ''u'' da ''Q'' ;
14 '''if''' dist[''u''] = infinito:
15 '''break''' ; ''// tutti i vertici rimanenti sono''
16 '''end if''' ''// inaccessibili dal nodo sorgente''
17
18 '''For each''' neighbour ''v'' di ''u'': ''// dove v non è ancora stato''
19 ''// rimosso da Q.''
20 ''alt'' := dist[''u''] + dist_tra(''u'', ''v'') ;
21 '''if''' ''alt'' < dist[''v'']: ''// Rilascia (u,v,a)''
22 dist[''v''] := ''alt'' ;
23 precedente[''v''] := ''u'' ;
24 decrease-key ''v'' in ''Q''; ''// Riordina v nella coda''
25 '''end if'''
26 '''end for'''
27 '''end while'''
28 '''return''' dist;
Se siamo interessati solo al percorso minimo tra due vertici <code><var>sorgente</var></code> e <code><var>destinazione</var></code>, possiamo terminare la ricerca alla riga 13 se <code><var>u</var> = <var>destinazione</var></code>.
Adesso possiamo leggere il percorso più breve da <code><var>sorgente</var></code> a <code><var>destinazione</var></code> tramite un'iterazione inversa:
1 ''S'' := sequenza vuota
2 ''u'' := ''destinazione''
3 '''while''' precedente[''u''] è definito: ''// Costruisci il cammino minimo con uno stack S
4 inserisci ''u'' all'inizio di ''S'' ''// Esegui il push del vertice sullo stack
5 ''u'' := precedente[''u''] ''// Traverse da destinazione a sorgente.
6 '''end while''' ;
Adesso la sequenza <code><var>S</var></code> è la lista dei vertici che costituiscono un cammino minimo da <code><var>sorgente</var></code> a <code><var>destinazione</var></code>, o la sequenza vuota se non ci sono percorsi minimi esistenti.
== Tempo di esecuzione ==
| 