Cammini di costo minimo
Università Roma Tre – Dipartimento di Matematica e Fisica IN440 – Ottimizzazione Combinatoria
Prof. Marco Liverani
Cammini di costo minimo
§
Dato un grafo G = (V, E) la lunghezza di un cammino p su G è data dal numero di spigoli che lo compongono§
Un cammino di lunghezza minima tra due vertici u e v di G può essere trovato in O(n + m) mediante una visita in ampiezza BFS da u o da v§
In diversi contesti applicativi è utile attribuire un costo, una capacità o un peso (in generale: un valorenumerico non negativo) agli spigoli del grafo, ottenendo così un grafo pesato dato dalla coppia (G, w) con w: E(G) ⟶ ℝ funzione costo/peso associata agli spigoli
§
Possiamo definire il costo di un cammino p: u ⤳ v come§
Il cammino di costo minimo dal vertice u al vertice v è quindi il cammino per cui risulta W(p) minimo;possiamo definire allora la distanza pesata d(u, v) tra due vertici u e v di G come
<latexit sha1_base64="dTu0ocOjV+3mK+sMD2Sq26K4TQM=">AAACHXicbVC7SgNBFJ2NrxhfUUsLB4OSgIRdC7URghZaRjAPSJZldjJJhszODjOz0bCkFOz8BHtttbG3E1vxC/wNJ4mFSTxw4cw593LnHl8wqrRtf1mJmdm5+YXkYmppeWV1Lb2+UVZhJDEp4ZCFsuojRRjlpKSpZqQqJEGBz0jF75wN/EqXSEVDfqV7grgBanHapBhpI3np7UpW5OAJrKso8OJstN/N1SmHog+vhw8vnbHz9hBwmji/JFNwzl/v9h7vi176u94IcRQQrjFDStUcW2g3RlJTzEg/VY8UEQh3UIvUDOUoIMqNh4f04a5RGrAZSlNcw6H6dyJGgVK9wDedAdJtNekNxP+8WqSbx25MuYg04Xi0qBkxqEM4SAU2qCRYs54hCEtq/gpxG0mEtclubItQDGly00+ZZJzJHKZJ+SDvHOadSydTOAUjJMEW2AFZ4IAjUAAXoAhKAINb8ASewYv1YL1Z79bHqDVh/c5sgjFYnz/TOqP6</latexit>
W (p) = Â(u,v)2pw(u,v)
<latexit sha1_base64="F29M4BwYYuQHX2wOYZgJ4d8RRFc=">AAADHHicbVLLihNBFL3dOjrGV9Slm8KMoiCh24UzDAhBF7ocwUwC6RCqqyuZYqq6m6rqMKHpnSs3/oFbwZWgnzA7cSv4Bf6Gt6qDOJkpqO5zz73n3HqlpRTGRtHvILx0eevK1e1rnes3bt663b1z99AUlWZ8yApZ6HFKDZci50MrrOTjUnOqUslH6fErlx8tuTaiyN/ZVcmnii5yMReMWqSK7kf4DBnMoIYKnsISGiDwAmcCKXBYgIAccwwoGIwN5juoSED5jNOVsI9ap5BYQdHNgIUCmdZtBI+x5gmiR77KYtUJfmvvSLyr8BoXVehKfD+17uGcdtBhB/8Z8i6qfNTiJc4GfZP1ypxmjm6rCzpSXKMFjTUKuRyx+LcjF2ebe511e1E/8oOcB/Ea9Ab7r7+ejj9sHcy6f5KsYJXiuWWSGjOJo9JOa6qtYJI3naQyvKTsmC74BGFOFTfT2t9jQx4ik5F5oXHmlnj2f0VNlTErlWKlovbIbOYceVFuUtn53rQWeVlZnrO20bySxBbEPQqSCc2ZlSsElGmBayXsiGrKLD6dM11KI6nlJ407mXjzHM6Dw2f9+Hk/fhv3Bi+hHdtwHx7gm4hhFwbwBg5gCCx4H3wJvgXfw0/hafgj/NmWhsFacw/OjPDXX4UqzdE=</latexit>
du,v =
(minp:u vW (p) se esiste un cammino p da u a v
• altrimenti
Cammini di costo minimo
§
La distanza pesata tra i vertici così definita soddisfa la disuguaglianza triangolare (è la principale caratteristica delle distanze sugli spazi metrici): d(u,v) ≤ d(u,z) + d(z,v)§
Un cammino di costo minimo è un cammino semplice: se tutti i pesi assegnati agli spigoli di G sono positivi, allora eventuali cicli presenti nel cammino ne aumentano inutilmente il costo§
Prop.: Ogni cammino di costo minimo gode della proprietà di sottostruttura ottima: se p: u ⤳ v è uncammino di costo minimo da u a v e u’, v’ ∈ p, allora il sotto-cammino p’ di p definito come p’: u’ ⤳ v’ è un cammino di costo minimo da u’ a v’
Dimostrazione: Se per assurdo p’ non fosse un cammino minimo da u’ a v’ allora ne esisterebbe un altro costo
inferiore: p*: u’ ⤳ v’ e quindi anche p non sarebbe un cammino di costo minimo da u a v, contraddicendo l’ipotesi ∎
v
s u
p2 W(p2) > 0 p1
p3
Cammini di costo minimo
§
Fissato un vertice sorgente s ∈ V(G) si può definire un albero orientato composto da cammini di costo minimo da s in ogni altro vertice v ∈ V(G): per la proposizione precedente, infatti, è possibile scegliere fra i cammini di costo minimo quelli che non creano dei cicli§
È utile osservare che un albero di cammini di costo minimo non è necessariamente un albero ricoprente di costo minimo; per dimostrarlo basta esibire un esempio in cui si osserva la differenzau v
s 10
20 20
Un grafo G
u v
s
20 20
Un albero di cammini di costo minimo su G con sorgente in s
u v
s 10
20
Un albero ricoprente di costo minimo su G
Cammini di costo minimo
§
Condizione di Bellmann: Sia (G, w) un grafo orientato pesato con funzione costo w; allora per ogni (u, v) ∈ E(G) e ogni vertice z ∈ V(G) risulta d(z, v) ≤ d(z, u) + w(u, v)§
Problemi sui cammini di costo minimo:• Cammini minimi con sorgente singola: fissata una singola sorgente s ∈ V(G), trovare il cammino di costo minimo p: s ⟶ v per ogni v ∈ V(G)
• Cammini minimi verso una singola destinazione: fissato un singolo vertice di destinazione t ∈ V(G), trovare il cammino minimo p: v ⟶ t per ogni v ∈ V(G)
• Cammini minimi fra tutte le coppie: per ogni coppia di vertici u, v ∈ V(G) trovare il cammino di costo minimo che li collega
• Cammino di costo minimo fra una coppia di vertici: fissati due vertici u, v ∈ V(G) trovare un cammino di costo minimo che li collega
z v
u p1
p2
Algoritmo di Dijkstra
§
È forse l’algoritmo più noto per la soluzione del problema dei cammini di costo minimo da una sorgente singola§
L’autore, da cui prende il nome, Edsger Wybe Dijkstra è stato un celeberrimo informatico olandese, che ha operato a lungo presso l’Università del Texas negli Stati Uniti; nel 1972 ha vinto il Premio Turing per i suoi contributi fondamentali all’informatica teorica•
Sul sito https://www.cs.utexas.edu/users/EWD/ è disponibile una vasta raccolta delle sue dispense e dei suoi articoli, scritti con precisione ed eleganza con una macchina da scrivere§
La dinamica dell’algoritmo si basa sul principio del rilassamento:•
sia p1: s ⤳ u un cammino da s a u con costo W(p1) e p2: s ⤳ v un cammino da s a v con costo W(p2); supponiamo che (u, v) ∈ E(G) con costo w(u, v)•
se W(p1) + w(u, v) < W(p2) allora per andare da s a v conviene scegliere il cammino che passa per u, invece di usare il cammino p2Edsger W. Dijkstra (1930 – 2002)
s
p v
w(u,v)
p2
Algoritmo di Dijkstra
§
Partendo dalla sorgente s fornita in input, l’algoritmo di volta in volta prende in esame il vertice più «vicino» alla sorgente tra quelli ancora da elaborare e applica il principio delrilassamento a tutti i vertici adiacenti
§
L’algoritmo di Dijkstra utilizza una coda di priorità perscegliere il vertice di G da prendere in esame di volta in volta, utilizzando il costo del cammino minimo di ciascun vertice come valore su cui costruire la priorità degli elementi della coda: a costo più basso corrisponde priorità più alta
§
Naturalmente, fino a quando non sono stati raggiunti ed elaborati, i vertici v ∈ V(G) hanno una stima del costo del cammino minimo pari a Ds,v = ∞; solo la sorgente ha Ds,s = 0§
La coda di priorità viene implementata con una struttura dati di heap binario: un albero binario completo in cui l’elemento di priorità massima si trova sulla radice e ciascun vertice ha una priorità maggiore dei propri figliUn heap binario H
5
10 6
20 90 ∞ 40
95 ∞ 93
Radice: elemento di priorità massima
Elementi di bassa priorità
§
In un heap binario le operazioni di inserimento e di estrazione di unelemento e di modifica della priorità di
Ds,v
Algoritmo di Dijkstra
1
3 4
2
5 6
8 9
7
10
20 60 10
40 20
20 10
40 20 5 10
60 50
70
10 20
10 5
30
0 ∞ ∞ ∞ ∞ ∞ ∞
Q 1 2 3 4 5 6 7 8 9 102 3 4 5 6 7 8 9 10 20 60 10
4 2 3 5 6 7 8 9 10
20 2 3 5 6 7 8 9 10
50 ∞ 50∞ ∞
2 6 3 9 5 7 8 10 10 20
6 3 9 5 7 8 10
1
2 3 4
5 6
9
7 8
10
40 25 80
6 5 3 9 7 8 10 5 3 9 7 8 10
20 40
3 9 7 8 10
25
35 45 95
9 7 8 10 35 7 8 10
40 70 50
8 10
45 55
10
50 55 Complessità algoritmo di Dijkstra: O(m log2 n),
Algoritmo di Bellman-Ford
§
Proposto indipendentemente da Lester Ford jr. nel 1954 e da Richard Bellman nel 1958, l’algoritmo di Bellman-Ford risolve il problema del cammino minimo da una sorgente singola§
Si basa sul principio del rilassamento e sulla considerazione che un qualsiasi cammino di costo minimo su un grafo G non può avere più di n – 1 spigoli, se il grafo ha n vertici e non contiene cicli di peso negativo§
Ha una complessità computazionale superiore all’algoritmo di Dijkstra, ma può essere applicato anche su grafi con pesi negativi (purché non siano presenti cicli di costo negativo)§
Siccome ogni spigolo può comparire al massimo una volta nel cammino di costo minimo da s ad ogni vertice v del grafo, dopo aver valutato il contributo di ogni spigolo per n − 1 volte, sarà stato certamente individuato il cammino di costo minimo per ciascun vertice del grafo§
Se invece, iterando il ciclo principale ancora una volta, qualche vertice riduce ulteriormente la sua stima di costo minimo da s, allora significa che nel grafo è presente un ciclo di costo negativoRichard Bellman (1920 – 1984)
Lester Ford jr.
(1927 – 2017)
7
10 5
20 10
Algoritmo di Bellman-Ford
8
–5
4
4
1 2 3 4 5 6
Ds,v 0 10∞ 1813∞ 2519∞ 25∞ 2015∞ 1
2
6
4 3
5
Se esiste, identifica un ciclo di costo negativo
§
Viene eseguito per n – 1 volte un ciclo che itera su tutti gli m spigoli del grafo (righe 6-10): la complessità è O(n×m)Ottimizzazione dell’algoritmo di Bellman-Ford
§
L’algoritmo può essere reso più efficiente scegliendo opportunamente l’ordine con cui considerare gli spigoli§
Se il grafo è orientato e aciclico (DAG – directed acyclic graph) allora scegliendo i vertici nell’ordine topologico e gli spigoliuscenti da tali vertici in un ordine qualsiasi, si riduce drasticamente la complessità
dell’algoritmo: non è necessario considerare più volte lo stesso spigolo
§
In questo caso la complessità computazionale è O(n + m)Ordinamento topologico dei vertici di un DAG
§
Un ordinamento topologico dei vertici di un grafo orientato aciclico (DAG) è una relazione d’ordine tale che, per ogni u, v ∈ V(G) se (u, v) ∈ E(G) allora u ≤ v§
L’ordinamento topologico non può essere definito se il grafo contiene dei cicli§
Considerando il grafo in figura l’ordinamento topologico deve tenere conto delle seguenti disuguaglianze:1 ≤ 2, 1 ≤ 6, 2 ≤ 3, 2 ≤ 6, 3 ≤ 4, 3 ≤ 5, 3 ≤ 6, 4 ≤ 5, 6 ≤ 5
§
Un possibile ordinamento topologico è quindi: 1, 2, 3, 6, 4, 5§
L’ordinamento topologico è una relazione d’ordine parziale: può non essere unico (ad esempio anche: 1, 2, 3, 4, 6, 5)1
2
6
4 3
5
Ordinamento topologico dei vertici di un DAG
§
Un ordinamento topologico dei vertici di un grafo G orientato aciclico lo si può ottenere con una visita in profondità di G (DFS), tenendo conto dei tempi di fine visita di ciascun vertice: l’ordinamento topologico è dato dai tempi di fine visita in ordine decrescente§
La complessità di tale procedimento è O(n + m)§
In alternativa si può utilizzare l’algoritmo in figura: si calcola il grado entrante di ogni vertice, quindi si costruisce una coda Q con cui si definisce l’ordinamento topologico di V(G)§
Si smantella progressivamente il grafo G(o una sua copia G’) eliminando i vertici privi di spigoli entranti e accodandoli a Q, finché il grafo è vuoto e la coda Q contiene tutti i suoi vertici
§
Complessità: O(n log2 n + m) se si gestiscono i vertici di G’ in una coda di priorità (heap binario) in base al numero di spigoli entrantiOrdinamento topologico dei vertici di un DAG
1
2
6
4 3
5
1
2
6
4 3
5
G G’
Q
1
1
2
1 2
3
6
4 5
1 2 3
1 2 3 6
1 2 3 6 4
1 2 3 6 4 5
Programmazione dinamica
§
La programmazione dinamica è una tecnica generale per la risoluzione di problemi di ottimizzazionecombinatoria; la applicheremo al problema del cammino di costo minimo fra tutte le coppie di vertici di G
§
Questa tecnica è stata introdotta da Bellman negli anni ‘40§
Si può applicare solo se il problema gode della proprietà di sottostruttura ottima della soluzione (come nel caso del problema del cammino di costo minimo)§
Il procedimento è di tipo bottom-up (divide et impera è top-down):•
a partire dalla soluzione di sottoproblemi elementari (il cammino di costo minimo fra vertici adiacenti, adesempio) si aggregano le soluzioni, calcolando la soluzione ottima di problemi sempre più grandi, fino a risolvere il problema originario
•
il procedimento si basa su un’espressione ricorsiva con cui si calcolano in successione le soluzioni dei problemi più grandi, basandosi sulle soluzioni di quelli più piccoli calcolate ai passi precedenti•
in questo modo viene calcolata una sequenza di matrici quadrate di ordine n, A(1), A(2), ..., A(n) conun’espressione ricorsiva del tipo A(k) = f(A(k – 1)), per k > 1 e costruendo a priori A(1) in modo diretto con dei valori costanti
•
Gli elementi Ai, j(k) delle matrici quadrate rappresentano, al passo k del procedimento risolutivo, il costo minimo, fin qui calcolato, per un cammino dal vertice v al vertice vProgrammazione dinamica
§
Indichiamo con w(vi, vj) il costo dello spigolo (vi, vj) ∈ E(G); in questo modo si può definire una matrice quadrata W di ordine n:§
Per applicare la tecnica della programmazione dinamica costruiremo una successione di matrici L(0), L(1), ..., L(k), ..., L(n – 1)§
L’elemento generico della matrice li, j(k) rappresenta il costo del cammino di costo minimo da vi a vj definito utilizzando al più k spigoli (il costo cammino di lunghezza minore o uguale a k)<latexit sha1_base64="IJ9yZarwvOTAOJzKNzOhDKlGaAc=">AAACrHicbVHLatwwFJXdV+r0MX3surk0bZlAGOwu2lIYCE1Lu0whkwmMjZE11xNNZMlI8jSD8S91mR/IV+QL8gXtuppHaeL0guBwzrkPjrJScGPD8MLzb92+c/fexv1g88HDR487T54eGlVphgOmhNJHGTUouMSB5VbgUamRFpnAYXayt9CHM9SGK3lg5yUmBZ1InnNGraPSzs9hWvOdaQN9iDOccFkzN800QQhvIC4ydVqDQWhglvL+LJ3GcfCj6/COw9styz8+5hK+dL9uO7eDuZ23nBxiqWwfpn/ZVrsTr45AOV6flXa2wl64LLgJojXY2n316+x8tvl7P+1cxmPFqgKlZYIaM4rC0iY11ZYzgU0QVwZLyk7oBEcOSlqgSeplrg28dswYcqXdkxaW7NWOmhbGzIvMOQtqj01bW5D/00aVzT8kNZdlZVGy1aK8EmAVLD4Jxlwjs2LuAGWau1uBHVNNmXVfeW1LaQS1eNoELpmoncNNcPi2F73rRd9dRJ/IqjbIC/KSdElE3pNd8o3skwFh3nPvo7fnffZ7/oE/8pOV1ffWPc/ItfLzPzT+0UM=</latexit>
Wi, j = 8>
<
>:
0 se vi = vj
w(vi,vj) se (vi,vj) 2 E(G)
• se i 6= j e (vi,vj) 62 E(G)
<latexit sha1_base64="T1LUT/iu2iTB0SN85Zw/wXoaWdk=">AAACWHicbVBdSxtBFL1ZbdWtral97MvQ0GJBwq4PthSE0L74qNCoNBvD7ORuHJ2dXWbuimHY/9EfUuhr/0b9Ae1j/QnOJnnwowcGDufce+5w0lJJS1H0uxUsLT95urK6Fj5bf/5io/1y88gWlRHYF4UqzEnKLSqpsU+SFJ6UBnmeKjxOL740/vElGisL/ZWmJQ5zPtEyk4KTl0btb2rk5PZ5feq2ovc12wuTFCdSO+EzbR1G7B1LCK/IMYuslnvnSRImUmc0bZw8La4c44qMzFGTrMME9XixPGp3om40A3tM4gXp9LqffvzcPvx+MGr/TcaFqJokobi1gzgqaei4ISkU+uzKYsnFBZ/gwFPNc7RDN+ugZm+9MmZZYfzTxGbq3Q3Hc2uneeonc05n9qHXiP/zBhVlH4dO6rIi1GJ+KKsUo4I1hbKxNChITT3hwkj/VybOuOGCfO33rpRWcd9lHfpm4oc9PCZHO914txsfxp3eZ5hjFV7DG9iCGD5AD/bhAPog4Bf8gX9w07oOIFgJ1uajQWux8wruIdi8BRkPuFI=</latexit>
li, j(0) =
(0 se i = j
• altrimenti
<latexit sha1_base64="/gBtRSZ8bPx8JJr1AbtA+yv1NFM=">AAACrnicbVHbihNBEO0Zb2u8RQVffCkMSgIhzPjgLmIgKKs+7oLJLmTGoadTk3S2p3vo7okbhvkPP8MHwW/xC/wNO8kuZrMWFBzOOXWhKi0ENzYIfnv+jZu3bt/Zu9u4d//Bw0fNx09GRpWa4ZApofRpSg0KLnFouRV4WmikeSrwJD37sNJPFqgNV/KLXRYY53QqecYZtY5Kmj/E16odduqk4t15DX2IUpxyWTHX09SNAF5BlKfqvAKDUAPvz6Oo8a29SHh3kcw7O/I/PuISDtufOs7tYGaX207XByKpbB/ml+ROtRO3O6CcXG6UNFtBL1gHXAfhBWgNem9//uoefz9Kmn+iiWJljtIyQY0Zh0Fh44pqy5nAuhGVBgvKzugUxw5KmqOJq/Vla3jpmAlkSruUFtbsdkVFc2OWeeqcObUzs6utyP9p49JmB3HFZVFalGwzKCsFWAWrN8GEa2RWLB2gTHO3K7AZ1ZRZ98wrUwojqMXz9WXC3TtcB6PXvfBNLzwOW4P3ZBN75Dl5QdokJPtkQD6TIzIkzHvmvfMOvY9+4I/82E82Vt+7qHlKroQ/+wt2XdBk</latexit>
li, j(1) = 8>
<
>:
0 se i = j
w(vi,vj) se (vi,vj) 2 E(G)
• sei 6= j e (vi,vj) 62 E(G)
Programmazione dinamica
§
In generale si ha (espressione ricorsiva per l’algoritmo di programmazione dinamica):§
Il procedimento parte da li, j(0) e rilassa man mano il vincolo sulla massima lunghezza di un cammino di costo minimo, fino a n – 1 (massima lunghezza di un cammino di costo minimo, quindi privo di cicli)<latexit sha1_base64="T1LUT/iu2iTB0SN85Zw/wXoaWdk=">AAACWHicbVBdSxtBFL1ZbdWtral97MvQ0GJBwq4PthSE0L74qNCoNBvD7ORuHJ2dXWbuimHY/9EfUuhr/0b9Ae1j/QnOJnnwowcGDufce+5w0lJJS1H0uxUsLT95urK6Fj5bf/5io/1y88gWlRHYF4UqzEnKLSqpsU+SFJ6UBnmeKjxOL740/vElGisL/ZWmJQ5zPtEyk4KTl0btb2rk5PZ5feq2ovc12wuTFCdSO+EzbR1G7B1LCK/IMYuslnvnSRImUmc0bZw8La4c44qMzFGTrMME9XixPGp3om40A3tM4gXp9LqffvzcPvx+MGr/TcaFqJokobi1gzgqaei4ISkU+uzKYsnFBZ/gwFPNc7RDN+ugZm+9MmZZYfzTxGbq3Q3Hc2uneeonc05n9qHXiP/zBhVlH4dO6rIi1GJ+KKsUo4I1hbKxNChITT3hwkj/VybOuOGCfO33rpRWcd9lHfpm4oc9PCZHO914txsfxp3eZ5hjFV7DG9iCGD5AD/bhAPog4Bf8gX9w07oOIFgJ1uajQWux8wruIdi8BRkPuFI=</latexit>
li, j(0) =
(0 se i = j
• altrimenti
<latexit sha1_base64="/gBtRSZ8bPx8JJr1AbtA+yv1NFM=">AAACrnicbVHbihNBEO0Zb2u8RQVffCkMSgIhzPjgLmIgKKs+7oLJLmTGoadTk3S2p3vo7okbhvkPP8MHwW/xC/wNO8kuZrMWFBzOOXWhKi0ENzYIfnv+jZu3bt/Zu9u4d//Bw0fNx09GRpWa4ZApofRpSg0KLnFouRV4WmikeSrwJD37sNJPFqgNV/KLXRYY53QqecYZtY5Kmj/E16odduqk4t15DX2IUpxyWTHX09SNAF5BlKfqvAKDUAPvz6Oo8a29SHh3kcw7O/I/PuISDtufOs7tYGaX207XByKpbB/ml+ROtRO3O6CcXG6UNFtBL1gHXAfhBWgNem9//uoefz9Kmn+iiWJljtIyQY0Zh0Fh44pqy5nAuhGVBgvKzugUxw5KmqOJq/Vla3jpmAlkSruUFtbsdkVFc2OWeeqcObUzs6utyP9p49JmB3HFZVFalGwzKCsFWAWrN8GEa2RWLB2gTHO3K7AZ1ZRZ98wrUwojqMXz9WXC3TtcB6PXvfBNLzwOW4P3ZBN75Dl5QdokJPtkQD6TIzIkzHvmvfMOvY9+4I/82E82Vt+7qHlKroQ/+wt2XdBk</latexit>
li, j(1) = 8>
<
>:
0 se i = j
w(vi,vj) se (vi,vj) 2 E(G)
• sei 6= j e (vi,vj) 62 E(G)
<latexit sha1_base64="AcCqFlF6VDUgVB2e8ENwI1Xidtw=">AAACvnicnVHLbhMxFPUMrxJeKSzZWFSgRIRohkXLBim0GxYsikTSSpkw8jh3Eiu2Z7DvhCaj4ae6r/gNFqz5DZxJVKUtK45k++iec32t4ySXwmIQ/PL8W7fv3L23c7/x4OGjx0+au08HNisMhz7PZGZOE2ZBCg19FCjhNDfAVCLhJJkdrfSTORgrMv0FFzmMFJtokQrO0JXi5k8Zl0VnXn0tW7N2Rd/TSAkdSUgxKrekN2G76tRaXIZO/kaX9a4rum1eXprpa/q9tezM25ERkylG1eUZNX5sYzPyf69txM29oBvUoDdJuCF7vQ/B+e/dC30cN/9E44wXCjRyyawdhkGOo5IZFFxC1YgKCznjMzaBoaOaKbCjsk66oi9dZUzTzLilkdbV7Y6SKWsXKnFOxXBqr2ur4r+0YYHpu1EpdF4gaL4elBaSYkZX30bHwgBHuXCEcSPcWymfMsM4us+9MiW3kiGc1cmE13O4SQZvu+F+N/zsIjoka+yQ5+QFaZGQHJAe+UiOSZ9w75X3yet7A7/np77ys7XV9zY9z8gV+Gd/AXnT3R0=</latexit>
lu,v(k) = min
⇢
lu,v(k 1), min
1zn
nlu,z(k 1)+w(z,v)o
= min
1zn
nlu,z(k 1)+w(z,v)o
perché w(v, v) = 0 per ogni v ∈ V(G)
Cammini di costo minimo fra tutte le coppie
§
Osserviamo che L(1) = W§
Inoltre, un cammino di peso minimo tra u e v su un grafo G = (V, E) con |V(G)| = n non può avere più di n – 1 spigoli quindi il costo del cammino di costo minimo da u a v è𝛿(u, v) = lu,v(n – 1)
§
Deve risultare lu,v(h) = lu,v(n – 1) per ogni h ≥ n, perché il cammino minimo è semplice (inassenza di cicli negativi, come nel nostro caso)
§
Se il cammino di costo minimo da u a v ha h spigoli, allora lu,v(h) è il costo del cammino minimo e risulta lu,v(h) = lu,v(q) per ogni q > h§
La complessità dell’algoritmo è O(n4)Cammini di costo minimo fra tutte le coppie
L(1) 1 2 3 4 5 6
1 0 10 ∞ ∞ ∞ 20
2 ∞ 0 8 ∞ ∞ 5
3 ∞ ∞ 0 7 ∞ –5
4 ∞ ∞ ∞ 0 10 ∞
5 ∞ ∞ 4 ∞ 0 ∞
6 ∞ ∞ ∞ ∞ 4 0
7
10 5
20 10
–5
4
1 4
2
6
4 3
5
8
Cammini di costo minimo fra tutte le coppie
L(2) 1 2 3 4 5 6
1 0 10 18 ∞ ∞ 15
2 ∞ 0 8 15 9 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 ∞
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 ∞ 4 0
L(1) 1 2 3 4 5 6
1 0 10 ∞ ∞ ∞ 20
2 ∞ 0 8 ∞ ∞ 5
3 ∞ ∞ 0 7 ∞ –5
4 ∞ ∞ ∞ 0 10 ∞
5 ∞ ∞ 4 ∞ 0 ∞
6 ∞ ∞ ∞ ∞ 4 0
Cammini di costo minimo fra tutte le coppie
L(3) 1 2 3 4 5 6
1 0 10 18 25 ∞ 13
2 ∞ 0 8 15 7 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 9
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 15 4 0
L(2) 1 2 3 4 5 6
1 0 10 18 ∞ ∞ 15
2 ∞ 0 8 15 9 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 ∞
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 ∞ 4 0
Cammini di costo minimo fra tutte le coppie
L(4) 1 2 3 4 5 6
1 0 10 18 25 7 13
2 ∞ 0 8 15 7 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 9
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 15 4 0
L(3) 1 2 3 4 5 6
1 0 10 18 25 ∞ 13
2 ∞ 0 8 15 7 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 9
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 15 4 0
Cammini di costo minimo fra tutte le coppie
L(5) 1 2 3 4 5 6
1 0 10 18 25 7 13
2 ∞ 0 8 15 7 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 9
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 15 4 0
L(4) 1 2 3 4 5 6
1 0 10 18 25 7 13
2 ∞ 0 8 15 7 3
3 ∞ ∞ 0 7 –1 –5
4 ∞ ∞ 14 0 10 9
5 ∞ ∞ 4 11 0 –1
6 ∞ ∞ 8 15 4 0
Cammini di costo minimo fra tutte le coppie
§
Con l’algoritmo appena visto calcoliamo il costo del cammino di costo minimo, ma non lasciamo traccia di quale sia tale cammino§
Per tracciare i cammini di costo minimopossiamo definire una successione di matrici 𝛱(k) il cui generico elemento 𝜋ij(k) indica il padre del vertice vj nel cammino da vi a vj con al più k spigoli
§
Per questo occorre modificare l’algoritmo aggiungendo a riga 2: 𝜋ij(k) = null per ogni vi, vj ∈ V(G)§
Inoltre l’istruzione a riga 8 deve essere sostituita con le seguenti:Una versione più efficiente dello stesso algoritmo
§
Nell’algoritmo appena visto la tecnica della programmazione dinamica è utilizzataincrementando di volta in volta di un solo spigolo la massima lunghezza dei cammini di costo minimo
§
Per accelerare l’esecuzione dell’algoritmo si può procedere aggregando le soluzioni di due problemi di dimensione pari alla metà della dimensione del problema che stiamoconsiderando
§
Anziché aumentare solo di 1 la dimensione del problema considerato, possiamo raddoppiarne la dimensione ad ogni passo):§
La complessità dell’algoritmo diventa:Algoritmo di Floyd-Warshall
§
L’algoritmo utilizza la tecnica della programmazione dinamica e fu pubblicato indipendentemente da Floyd e da Warshall nel 1962 su Communication of the ACM e sul Journal of the ACM§
Sia p: u ⤳ v un cammino da u a v dato da p = ⟨v1, v2, ..., vk⟩, con u = v1 e v = vk; i vertici v2, ..., vk – 1 sono intermedi in p§
Consideriamo tutti i cammini da u a v con vertici intermedi in {1, 2, ..., k}; sia p un cammino di costo minimo tra questi§
L'algoritmo di Floyd e Warshall per il calcolo dei cammini di costo minimo fra tutte le coppie di vertici di un grafo con pesi assegnati agli spigoli (e privo di cicli di costo negativo) si basa su alcune semplici considerazioni:•
se k non è un vertice intermedio di p allora i vertici intermedi di p sono tutti in {1, 2, ..., k – 1} e quindi un cammino minimo da u a v con vertici intermedi in {1, 2, ..., k – 1} è anche un cammino minimo da u a v con vertici intermedi in {1, 2, ..., k}•
se k è un vertice intermedio di p allora possiamo spezzare p in due sotto-cammini: p1: u ⤳ k e p2: k ⤳ v•
per la sottostruttura ottima dei cammini minimi risulta che p1 è un cammino minimo da u a k e che p2 è un cammino minimo da k a v con vertici intermedi in {1, ..., k}•
però è vero anche che sia p1 che p2 hanno vertici intermedi in {1, ..., k – 1}Robert W. Floyd (1936 – 2001)
Stephen Warshall (1935 – 2006)
Algoritmo di Floyd-Warshall
§
Sulla base delle considerazioni precedenti possiamo costruire il procedimento bottom-up su cui si basa l’algoritmo di Floyd e Warshall§
Sia duv(k) il peso del cammino da u a v con vertici intermedi in {1, 2, ..., k}; vale la seguente definizione ricorsiva per le matrici D(k) quadrate di ordine n:§
Visto che un cammino minimo da u a v è semplice e che sicuramente tutti i vertici intermedi si trovano in {1, ..., n} la matrice D(n) = (d(n)uv) fornisce la soluzione finale del problema, ossia risulta d(n)uv = 𝛿(u,v) per ogni u, v ∈ V(G)Algoritmo di Floyd-Warshall
§
Il procedimento iterativo per la costruzione delle matrici D(k) è molto semplice e si basa sulla definizione ricorsiva appena indicata§
La complessità dell’algoritmo è 𝛩(n3)§
L’algoritmo si presta bene ad unaimplementazione priva di strutture dati complicate: sono sufficienti delle matrici numeriche
Algoritmo di Floyd-Warshall
§
Integriamo l'algoritmo di Floyd-Warshall per calcolare anche i cammini costo minimo e non solo il costo di tali cammini§
Per far questo definiamo la matrice 𝛱(n) in cui 𝜋uv(n) rappresenta il predecessore di v nel cammino di costo minimo da u a v§
Il calcolo di 𝜋uv(n) si basa su 𝜋uv(n – 1) sostanzialmente con lo stesso schema di programmazione dinamica con cui sono state calcolate le distanze; la base del procedimento ricorsivo è la seguente:§
Al passo generico dell’algoritmo possiamo calcolare 𝜋uv(k) con la seguente espressione ricorsiva:Algoritmo di Floyd-Warshall
§
Possiamo riscrivere l’algoritmo di Floyd- Warshall nel modo seguente, consentendo così il calcolo del costo dei cammini minimi per ogni coppia di vertici u, v ∈ V(G)mediante la matrice D(n) ed anche la
ricostruzione dei cammini stessi, attraverso la matrice 𝛱(n)
§
La complessità dell’algoritmo è la medesima:𝛩(n3)
inizializzazione
calcolo
Algoritmo di Floyd-Warshall
§
I cammini di costo minimo vengono calcolati con l’algoritmo di Floyd-Warshall e sono rappresentati attraverso la matrice 𝛱(n) in cui sono indicati i rapporti padre-figlio o predecessore-successore tra i vertici nei diversicammini di costo minimo (𝜋uv(n) rappresenta il predecessore del vertice v nel cammino da u a v)
§
Per visualizzare il cammino di costo minimo dal vertice u al vertice v è possibile utilizzare il seguente algoritmo ricorsivo§
Scambiando l’ordine delle due istruzioni al passo 2 e al passo 3 si inverte l’ordine con cui sono visualizzati i vertici del camminoChiusura transitiva di un grafo orientato
§
La chiusura transitiva di un grafo G = (V, E) è un grafo G* = (V, E*), dove (u, v) ∈ E* se e solo se esiste un cammino p: u ⤳ v in G§
Warshall arrivò all’algoritmo di Floyd-Warshall proprio con l’obiettivo di risolvere il problema della chiusura transitiva di un grafo orientato1
2
6
4 3
5 G
1
2
6
4 3
5 G*
Chiusura transitiva di un grafo orientato
§
Per calcolare G* applichiamo un algoritmo di programmazione dinamica simile a quello di Floyd-Warshall, in cui operiamo la sostituzione «min ⟶ or» e «+ ⟶ and»§
Il processo bottom-up consente la costruzione di una sequenza di matrici quadrate T(k)con la seguente struttura ricorsiva§
e per k ≥ 1:§
Interpretando i valori 1 e 0 presenti nelle matrici come i valori logici «vero» e «falso», il significato dell’espressione è chiaro:• v è raggiungibile da u mediante un cammino con vertici intermedi in {1, ..., k}
• se v è raggiungibile da u con un cammino con vertici intermedi {1, ..., k – 1}
• oppure se esiste un cammino con vertici intermedi in {1, ..., k − 1} dal vertice u al vertice k ed esiste un cammino dal vertice k al vertice v con vertici intermedi in {1, ..., k − 1}
§
Iterando l’algoritmo di Floyd-Warshall così modificato, si giunge alla matrice T(n) che rappresenta la matrice diChiusura transitiva di un grafo orientato
§
Algoritmo di Floyd-Warshall modificato per il calcolo della chiusura transitiva G* di ungrafo orientato G
Algoritmi per cammini di costo minimo
§
Riepiloghiamo nella seguente tabella gli algoritmi analizzati per il problema del calcolo del cammino di costo minimo su un albero con pesi assegnati agli spigoliAlgoritmo Sorgente singola Tutte le coppie
Dijkstra O(m + n log2 n) O(nm + n2 log2 n)
Bellman – Ford (base) O(nm) O(n2m)
Bellman – Ford (DAG) O(n + m) O(n2 + nm)
All Pairs Shortest Path O(n4)
Fast All Pairs Shortest Path O(n3 log2 n)
Floyd – Warshall 𝛩(n3)
