Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 11:01, 30 giu 2006

Versione delle 11:02, 30 giu 2006

Riga 29:

Consideriamo un problema in cui si vuole calcolare il percorso minimo tra casa e il posto di lavoro. Schematizziamo tutti i possibili percorsi ed il relativo tempo di percorrenza (supponendo di voler calcolare il percorso più breve in fatto di tempo di percorrenza). I nodi A, B, C, D, E indicano le cittadine per cui è possibile passare. Ecco una schematizzazione della rete:

[[Immagine: Ricerca_operativa_percorso_minimo_01.gif|center]]

Dobbiamo ora assegnare ad ogni nodo un valore, che chiameremo “potenziale”, seguendo alcune regole:

*Ogni nodo ha, all’inizio potenziale <math>+ \infty </math> (che indichiamo con “inf”);

Riga 39:

*Quando si aggiorna il potenziale di un nodo si lascia quello minore (essendo un problema di percorso minimo).

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]]

Seguendo le regole appena fissate consideriamo il nodo con potenziale minore (“casa”) e lo rendiamo definitivo (colorandolo di rosso) ed aggiorniamo tutti i nodi adiacenti sommando l’attuale valore del potenziale (ovvero zero) al costo del percorso. Aggiorniamo i potenziali perché avevamo, nel caso di A, potenziale infinito mentre ora abbiamo potenziale 2. Ricordando che il potenziale minore è sempre preferibile. Vediamo come si è aggiornata la rete:

[[Immagine: Ricerca_operativa_percorso_minimo_03.gif|center]]

Bisogna ora considerare il nodo non definitivo (ovvero quelli scritti in nero) con potenziale minore (il nodo A). Lo si rende definitivo e si aggiornano i potenziali dei nodi adiacenti B e C. Indichiamo con una freccia da dove proviene il potenziale dei nodi resi definitivi.

[[Immagine: Ricerca_operativa_percorso_minimo_04.gif|center]]

Il nodo con potenziale minore ora è C. lo si rende definitivo e si aggiornano quelli adiacenti.

[[Immagine: Ricerca_operativa_percorso_minimo_05.gif|center]]

Va notato come il nodo D abbia ora potenziale 6 in quanto 6 è minore di 8 e quindi lo si aggiorna. Se avessimo avuto un valore maggiore di quello che già c’era lo avemmo lasciato invariato.

Rendiamo definitivo il nodo D e aggiorniamo il grafico:

[[Immagine: Ricerca_operativa_percorso_minimo_06.gif|center]]

Il nodo con potenziale minore restante è B e lo si rende definitivo aggiornando di conseguenza il grafico:

[[Immagine: Ricerca_operativa_percorso_minimo_07.gif|center]]

Resta da considerare il nodo E ed aggiornare “ufficio”.

[[Immagine: Ricerca_operativa_percorso_minimo_08.gif|center]]

Seguendo all’indietro le frecce si ottiene il percorso minimo che dista casa da ufficio che dista (come indicato dal potenziale) “10”.

[[Immagine: Ricerca_operativa_percorso_minimo_09.gif|center]]

Bisogna notare come questo algoritmo ci dia non solo la distanza tra il punto di partenza e quello di arrivo ma la distanza di tutti nodi da quello di partenza.