Valerio Cutini
a.a. 2013 / 2014
Università degli Studi di Pisa
insegnamento di
Tecnica Urbanistica
• Corso di laurea triennale in Ing. Edile
Ingegneria del Territorio
• Corso di laurea magistrale
in Ing. Idraulica,Trasporti e Territorio
Lezione n° 3.
Gli algoritmi del minimo percorso
valerio cutini
Il problema del minimo percorso
a.a. 2013-2014
Il problema della determinazione del più breve percorso
fra due punti di un sistema insediativo è fondamentale
nella modellistica territoriale
Al fine di evitare che si operi per tentativi, sono stati
introdotti metodi rigorosi per risolvere la questione
Tali metodi hanno una logica iterativa, ed hanno in
comune alcune caratteristiche:
sono oggettivi e ripetibili
forniscono i risultati nel minor numero possibile di passaggi
ogni singolo passaggio è determinato univocamente dal
precedente e determina univocamente il successivo
ogni singolo passaggio determina un avvicinamento alla
soluzione del problema
valerio cutini
Il problema del minimo percorso
a.a. 2013-2014
I metodi per la determinazione del più breve percorso
fra due punti di un sistema insediativo sono detti
algoritmi del minimo percorso (shortest path
algorithms)
Le loro caratteristiche di iteratività li rendono
agevolmente applicabili mediante software specifici
Per la comprensione del loro funzionamento, è utile
schematizzare un sistema insediativo mediante l’uso
di grafi
valerio cutini
I grafi
a.a. 2013-2014
I grafi sono un metodo di rappresentazione di un sistema,
particolarmente utile ad evidenziare le relazioni fra i suoi
singoli elementi
Un grafo è composto da nodi e da archi
un nodo (node, vertex) rappresenta un punto dello spazio
un arco (edge, line) rappresenta la relazione di collegamento
diretto (se esitente) fra due nodi
i/j
1
2
1
0
5
6
7
8
9
10
11
12
13
14
I grafi
-
-
3
-
-
-
-
-
-
-
-
-
-
2
-
0
3
2
-
-
-
-
-
-
-
-
-
-
3
-
3
0
-
2
-
-
-
-
-
-
-
-
-
4
3
2
-
0
2
-
-
-
-
-
-
-
-
-
5
-
-
2
2
0
4
-
-
-
-
-
-
-
-
6
-
-
-
-
4
0
1
-
-
1
5
3
-
-
7
-
-
-
-
-
1
0
-
-
-
-
-
-
-
8
-
-
-
-
-
-
-
0
2
1
-
-
-
-
9
-
-
-
-
-
-
-
2
0
-
-
-
-
-
10
-
-
-
-
-
1
-
1
-
0
-
-
-
-
11
-
-
-
-
-
5
-
-
-
-
0
-
-
-
12
-
-
-
-
-
3
-
-
-
-
-
0
2
2
13
-
-
-
-
-
-
-
-
-
-
-
2
0
-
14
-
-
-
-
-
-
-
-
-
-
-
2
-
0
valerio cutini
a.a. 2013-2014
1 2
3m
3
2m
2m
3m 2m
5
4
4m
2m
1
m
8
6
14
7 1m
9
1
m
2m 3m
10
5m
12
2m
11
13
3
4
valerio cutini
I grafi
a.a. 2013-2014
Un grafo si dice connesso se per ogni coppia di nodi (v, w)
c’è un percorso che li unisce
Un grafo si dice orientato se la relazione di
connessione non è simmetrica, ovvero se esiste
almeno una coppia di nodi (v,w) tali che il percorso che
li unisce P (v, w) ≠ P (w, v)
In un grafo, i singoli nodi possono essere nodi di
origine (source vertices) o di destinazione (sink
vertices) di percorsi
Negli algoritmi del minimo percorso, utilizzeremo
grafi connessi e non orientati
valerio cutini
Gli algoritmi del minimo percorso
a.a. 2013-2014
Due qualità sono richieste ad un algoritmo del minimo
percorso
fornire risultati completi ed esaustivi
fornire risultati con il minor numero di passaggi
Queste due qualità raramente coesistono
esistono metodi speditivi, ma chhe forniscono risultati
parziali ed incompleti
esistono metodi che forniscono risultati esaustivi, a prezzo di
un elevato numero di passaggi
In particolare, gli SPA si dividono in due famiglie
quelli che determinano il percorso più breve da un nodo a
tutti gli altri (single-source)
quelli che determinano il percorso più breve fra tutte le
possibili coppie di nodi (all pairs)
valerio cutini
a.a. 2013-2014
Gli algoritmi single-source:
l’algoritmo di Dijkstra
E.W. Dijkstra
L’algoritmo di Dijkstra è il
più noto e usato degli
algoritmi che
determinano il minimo
percorso da un unico
nodo i, assunto come
origine
valerio cutini
a.a. 2013-2014
Gli algoritmi single-source:
l’algoritmo di Dijkstra
La logica dei passaggi dell’algoritmo è la seguente:
Si assegna per ogni dij un valore di tentativo, ponendo:
per i=j, dij = 0
per i≠j, se esiste un collegamento diretto l0, dij = l0
per i≠j, se non esiste un collegamento diretto, dij = ∞
Fra tutti i collegamenti dij, si individua il minimo valore dik, e
lo si trasforma in valore definitivo
Si assume il nodo k come nodo perno (pivot) e lo si interpone
in tutti i collegamenti dij, sostituendo il valore della misura
risultante, nel caso sia minore della precedente. Ovvero:
se dik+dkj < dijk-1, dijk = dik+dkj
se dik+dkj ≥ dijk-1, dijk = dijk-1
Si procede, fino a che tutti i valori dei collegamenti non sono
diventati definitivi
valerio cutini
a.a. 2013-2014
Gli algoritmi all-pairs:
l’algoritmo di Floyd
Robert W. Floyd
L’algoritmo di Floyd è il più
noto e usato degli algoritmi
che determinano il minimo
percorso di connessione fra
tutte le possibili coppie i, j di
nodi di un grafo
valerio cutini
a.a. 2013-2014
Gli algoritmi all-pairs:
l’algoritmo di Floyd
La logica dei passaggi dell’algoritmo è la seguente:
Si costruisce la matrice dei collegamenti dij, ponendo:
per i=j, dij = 0
per i≠j, se esiste un collegamento diretto l0, dij = l0
per i≠j, se non esiste un collegamento diretto, dij = ∞
Alla k-esima iterazione, si interpone il nodo k fra i e j,
sostituendo il valore della misura risultante, nel caso sia più
breve della precedente. Ovvero:
se dik+dkj < dijk-1, dijk = dik+dkj
se dik+dkj ≥ dijk-1, dijk = dijk-1
Si procede per n iterazioni (n matrici), fino a che tutti i nodi k
non sono stati interposti