Algoritmo di Dijkstra: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 31:
[[Immagine: Ricerca_operativa_percorso_minimo_01.gif|center]]
Dobbiamo ora assegnare ad ogni nodo un valore, che chiameremo “potenziale”, seguendo alcune regole:
<div style="float:center; width:60%; padding:15px; background: #f5f8ff; border: 1px solid blue; margin-left:8px; margin-right:8px;margin-bottom:15px; text-align:left">
*Ogni nodo ha, all’inizio potenziale <math>+ \infty </math> (che indichiamo con “inf”);
*Il nodo di partenza (in questo caso “casa”) ha potenziale 0 (ovvero dista zero da se stesso);
Riga 38 ⟶ 39:
*I potenziali definitivi indicano la distanza di quel nodo da quello di partenza;
*Quando si aggiorna il potenziale di un nodo si lascia quello minore (essendo un problema di percorso minimo).
</div>
Vediamo in pratica come si risolve questo esercizio. Questa è la rete in cui sono indicati anche i potenziali:
[[Immagine: Ricerca_operativa_percorso_minimo_02.gif|center]]
| |||