Home

Federica EU

1/8

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

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

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

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

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

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

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