Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 23:36, 3 apr 2007

Versione delle 10:58, 12 apr 2007

Riga 3:

==Algoritmo matematico==

Supponiamo di avere un grafo con n vertici contraddistinti da numeri interi {1,2,...,n} e che 1 sia scelto come nodo di partenza. Il peso sull'arco che congiunge i nodi j e k è indicato con ''p(j,k)''. Ad ogni nodo, al termine dell'analisi, devono essere associate due etichette, ''f(i)'' che indica il peso totale del cammino (la somma dei pesi sugli archi percorsi per arrivare al nodo i-esimo) e ''J(i)'' che riportaindica il nodo sul cammino minimo che porta al nodoprecede i-esimo subitonel precedentecammino questo ultimominimo. Inoltre definiamo due insiemi ''S'' e ''T'' che contengono rispettivamente i nodi a cui sono già state assegnate le etichette e quelli ancora da scandire.

#''Inizializzazione''.