Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 23.Problemi di Cammino Minimo: esempio


Il Problema dello SPT: esempio, 1

Si consideri il grafo G=(V,A) rappresentato in Figura.

Applicando l’algoritmo Dijkstra, si risolva il problema dell’albero dei cammini minimi a partire dal nodo s=1 ai restanti 4 nodi.

Ad ogni nodo j di V viene associata la coppia [L(j),p(j)]

che viene aggiornata iterazione per iterazione.

Grafo orientato G=(V,A) con 5 nodi ed 8 archi. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

Grafo orientato G=(V,A) con 5 nodi ed 8 archi. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 2

Inizializzazione:

[L(s),p(s)]=[0,s];

M=+\infty ;

[L(j),p(j)]=[M,0], per ogni j in V diverso da s, come mostrato in Figura (a).

L’insieme S dei nodi etichettati permanentemente è vuoto, mentre Q=V={1,2,3,4,5}.

a) Inizializzazione; 
b) Prima iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

a) Inizializzazione; b) Prima iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 3

I iterazione:
\[ s=1=\mbox{arg}\displaystyle{\min_{j\in Q}L[j]}. \]

Dunque, il nodo 1 viene etichettato permanentemente ed estratto da Q (Q={2,3,4,5}).

Viene esplorata la stella uscente FS(1)={2,4,5}, al fine di eventualmente migliorare le etichette temporanee dei nodi ad esso adiacenti, come mostrato in Figura (b), in cui la presenza del pallino accanto a [L(1)=0,p(1)=1] indica che tale coppia è definitiva per il nodo 1.

Ora, S={1}, mentre
\[\delta_G^+(S)=\{(1,2),(1,4),(1,5)\}.\]

a) Inizializzazione; 
b) Prima iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

a) Inizializzazione; b) Prima iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 4

II iterazione:
\[ 5=\mbox{arg}\displaystyle{\min_{j\in Q}L[j]}. \]

Dunque, il nodo 5 viene etichettato permanentemente ed estratto da Q (Q={2,3,4}).

Viene esplorata la stella uscente FS(5)={2,3,4}, al fine di eventualmente migliorare le etichette temporanee dei nodi ad esso adiacenti, come mostrato in Figura (a).

Ora, S={1,5}, mentre

\[\delta_G^+(S)=\{(1,2),(1,4),(5,4),(5,2),(5,3)\}.\]

a) Seconda iterazione; 
b) Terza iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

a) Seconda iterazione; b) Terza iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 5

III iterazione:
\[ 4=\mbox{arg}\displaystyle{\min_{j\in Q}L[j]}. \]

Dunque, il nodo 4 viene etichettato permanentemente ed estratto da Q (Q={2,3}).

Viene esplorata la stella uscente FS(4)={3}, al fine di eventualmente migliorare le etichette temporanee dei nodi ad esso adiacenti, come mostrato in Figura (b).

Ora, S={1,5,4}, mentre
\[\delta_G^+(S)=\{(1,2),(5,2),(4,3),(5,3)\}.\]

a) Seconda iterazione; 
b) Terza iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

a) Seconda iterazione; b) Terza iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 6

IV iterazione:
\[ 2=\mbox{arg}\displaystyle{\min_{j\in Q}L[j]}. \]

Dunque, il nodo 2 viene etichettato permanentemente ed estratto da Q (Q={3}).

Viene esplorata la stella uscente FS(2), che risulta essere un insieme vuoto, come mostrato in Figura (a).

Ora, S={1,5,4,2}, mentre
\[\delta_G^+(S)=\{(4,3),(5,3)\}.\]

a) Quarta iterazione; 
b) Quinta iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

a) Quarta iterazione; b) Quinta iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 7

V iterazione:
\[ 3=\mbox{arg}\displaystyle{\min_{j\in Q}L[j]}. \]

Dunque, il nodo 3 viene etichettato permanentemente ed estratto da Q (Q è ora un insieme vuoto).

Viene esplorata la stella uscente FS(3) e si ottiene lo scenario mostrato in Figura (b).

Ora, S=V, mentre
\[\delta_G^+(S)=\emptyset.\]

a) Quarta iterazione; 
b) Quinta iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa

a) Quarta iterazione; b) Quinta iterazione. Tratto da M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova,1999. Rilucidate da Paola Festa


Il Problema dello SPT: esempio, 8

Essendo

\[ Q=\emptyset, \]

l’algoritmo termina e l’albero dei cammini minimi individuato è mostrato in Figura.

Albero dei 4 cammini minimi. Disegnata da Paola Festa

Albero dei 4 cammini minimi. Disegnata da Paola Festa


I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion