a2. Grafi pesati.md

---

$$G = (V, E)$$

$$w: E \to R$$

$$(u, V, w(u,v))$$

Tra tutti gli alberi di esplorazione cerchiamo l'albero di cammini minimi radicato in $V_0$ ossia$$\forall v, P=V_o \sim > v : w(P) \text{ minimo}$$

Per i grafi pesati lo shortest path corrisponde al cammino di costo minimo rispetto al peso degli archi.

title: Perché abbiamo un albero di cammini minimi?

Supponiamo per iniziare che tutti i cammini siano distinti (non abbiamo contraddizione perché è  ancora un albero).

Se 2 cammini condividono un nodo, supponendo per assurdo che i 2 cammini siano distinti fino al nodo condiviso, possiamo riscriverli.

Essendo i due cammini ottimi i costi dei due percorsi devono essere uguali (altrimenti si invalida l'ottimalità di uno dei due).

Essendo uguali possiamo eliminare uno dei due cammini così da ottenere l'albero dei cammini minimi

title: Osservazione

I cammini minimi sono semplici (non hanno cicli), se esistono cicli di costo negativo __non esiste__ soluzione al cammino di costo minimo

Cammini Minimi Da Sorgente Singola

• $Q$: coda di priorità rispetto le etichette $d(v), \forall v \in V$
• $d(u) = \delta(s, u)$ quando $u$ è estratto da $Q$

Relax

Nuova Operazione per Ri-etichettare

relax(u, v, w(u,v)):
	if d(v) > d(u) + w(u,v):
		d(v) = d(u) + w(u,v)
		P(v) = u

Dijkstra

Il procedimento ricorda la [[a1. Grafi#Visita in Profondità (DFS-visit)|DFS]]

dijkstra(G, w*E->R+, s):
	for v in V:
		color(v) = white
		d(v) = + infinito
		P(v) = nil
	d(s) = 0
	sol = 0
	Q = makeQueue(d(v), V)
	while Q is not empty:
		u = extract_min(Q)
		for v in Adj(u) and v not in sol:
			relax(u, v, w(u,v))
		sol = sol + {u}

Decrease-key

decrease-key(H, i, key):
	H[i] = key
	while (i > 1) and (H[i] < H[i/2]):
		scambia(H[i], H[i/2])

Heap Relax

heap-relax(u, v, w(u, v)):
	if d(v) > d(u) + w(u, v):
		d(v) = d(u) + w(u, v)
		H(v) = u
		decrease-key(H, pos(v), d(v))

mantiene le etichette all'interno di un min-heap

• pos(v) corrisponde al nodo (i)
• d(v) corrisponde alla chiave

Senza mantenere una corrispondenza univoca tra i vertici del grafo e le loro posizioni in H

Dijkstra Con Heap

dijkstra(G, w*E->R+, s):
	for v in V:
		color(v) = white
		d(v) = + infinito
		P(v) = nil
	d(s) = 0
	sol = {}
	H = makeMinHeap(d(v) for v in V)
	while H in not empty:
		u = extract_min(H)
		for v in Adj(u) and v not in sol:
			heap-relax(u, v, w(u,v))
		sol = sol + {u}

è necessario stabilire una corrispondenza univoca tra i vertici del grafo e i nodi dell'heap

Per l'algoritmo di Dijkstra per il calcolo dei cammini minimi da sorgente singola è conveniente usare lo heap binario se il grafo è rappresentato con la lista delle adiacenze e $|E| \in O(\frac {V^2}{\log {|V|}})$

title: Correttezza


$$\forall v \in V: d(v)  = \delta (s, v), v \in sol$$

$d(s) = \delta (s,s) = 0$ passo base

$\exists \bar v$ primo nodo per cui $d(\bar u)  \neq \delta (s, \bar v))$ che è minimo della coda $d(w) \leq d(\bar v)$ perché estratto $v$ ho un cammino minimo quando estraggo $\bar u$ e il suo costo è maggiore di $d(\bar v)$

Dijkstra può tollerare archi di costo negativo **uscenti** dalla sorgente

![[Archi_neg.svg|center]]

```ad-note
title: Osservazione

$$s \sim u \to r$$
Se $(u,v) \in \delta (s, v)$
![[percorso_da_sorgente.svg|center]]

```

$\exists$ sicuramente un cammino minimo di un arco uscente da s, se $(s, v)$ $$d(s) = \delta (s,s)$$

Bellman-Ford

Se esistono archi con costo negativo c'è il rischio di avere dei cicli di costo negativo

BellmanFord(G, w: E -> R): boolean
	TRUE se esiste un ciclo negativo
	FALSE se non esiste

title: Osservazione

Se la lunghezza del cammino minimo $\geq n$ allora esiste un ciclo di costo negativo

BellmanFord(G = (V, E); w:V -> E):
	crea una lista L di tutti gli archi
	for i = 1:(|V| - 1)
		rilassa tutti gli archi in  L nell'ordine prestabilito
	for e = (u,v) in L:
		if d(v) > d(u) + w(u, v):
			return TRUE
	return FALSE

title: Correttezza

Se conosco che cammino ottimo da $s \to u$ è costituito dagli archi
$$(s, v) = e_1, e_2,...,e_r = (z, u)$$
e rilasso nell'ordine $$e_1,e_2,...,e_r$$ trovo il costo $d(u) = \delta(s, u)$

Non conosco l'ordine, per cui per ogni posizione $i$ provo tutti gli archi e sicuramente passerò per l'arco che è l'iesimo del cammino ottimo

I cammini minimi sono semplici, hanno $\leq n -1$ archi.

Se trovo da rilassare un arco in posizione $n$ allora esiste un cammino con un ciclo di costo negativo.

Complessità in Tempo

• creo la lista $|E|$
• rilasso tutti gli archi $|V| -1$ volte $$O(VE)$$
• rilasso ancora gli archi$$O(E)$$ Complessità: $O(VE)$, non dipende dalla rappresentazione.

Bellman-Ford è quindi più costoso di dijkstra, ma risolve il problema degli archi negativi

Cammini Minimi per Coppia Di Vertici

Soluzione 1

Basta chiamare Dijkstra o Bellman-Ford per ogni vertice

Soluzione 2

Algoritmi ad-hoc:

• Floyd-Warshall
• Metodo analogo alla moltiplicazione di matrici

Floyd Warshall

$$\forall i,j\quad d(i,j) = \delta(i, j)$$

Lavora in $n = |V|$ iterate, ad ogni iterata rende visibile un nodo nuovo

$$d^{(0)}(i, j) = \begin{cases} w(i,j) & (i, j) \in E\\ +\infty & (i, j) \notin E\\ 0&i=j \end{cases}$$

$$\Pi^{(0)}(i,j) = \begin{cases} i & (i,j) \notin E\\ nil & else \end{cases}$$

$$\Pi^{(1)}(i,j) = \begin{cases} \Pi^{(0)}(i,j)&d^{(1)}(i,j)= d^{(0)}(i,j)\\ \Pi^{(0)}(1, j)& d^{(1)}(i,j) = d^{(0)}(i,1) + d^{(0)}(1,j) \end{cases}$$ $$d^{(2)}(i,j) = i \sim {1, 2} \sim j$$ $$d^{(k)}(i,j) = \min{d^{(k-1)}(i, j), d^{(k-1)}(i, k) + d^{(k-1)}(k, j)}$$

collapse:open

![[EsempioFloyd.svg|center]]

| d0  |  1  |  2  |  3  |  4  |
|:---:|:---:|:---:|:---:|:---:|
|  1  |  0  |  3  |  +  |  1  |
|  2  |  3  |  0  |  2  |  1  |
|  3  |  +  |  2  |  0  |  1  |
|  4  |  1  |  1  |  1  | 0    |

| d1  |  1  |  2  |  3  |  4  |
|:---:|:---:|:---:|:---:|:---:|
|  1  |  0  |  3  |  +  |  1  |
|  2  |  3  |  0  |  2  |  1  |
|  3  |  +  |  2  |  0  |  1  |
|  4  |  1  |  1  |  1  |  0  | 

| d2  |  1  |  2  |  3  |  4  |
|:---:|:---:|:---:|:---:|:---:|
|  1  |  0  |  3  |  5  |  1  |
|  2  |  3  |  0  |  2  |  1  |
|  3  |  5  |  2  |  0  |  1  |
|  4  |  1  |  1  |  1  |  0  | 

| d3  |  1  |  2  |  3  |  4  |
|:---:|:---:|:---:|:---:|:---:|
|  1  |  0  |  3  |  5  |  1  |
|  2  |  3  |  0  |  2  |  1  |
|  3  |  5  |  2  |  0  |  1  |
|  4  |  1  |  1  |  1  |  0  |

| d4  |  1  |  2  |  3  |  4  |
|:---:|:---:|:---:|:---:|:---:|
|  1  |  0  |  2  |  2  |  1  |
|  2  |  2  |  0  |  2  |  1  |
|  3  |  2  |  2  |  0  |  1  |
|  4  |  1  |  1  |  1  |  0  |

$$d^2(1,3) = \min\{d^1(1,3) = +, \quad d^1(1,2) + d^1(2,3) = 5\} = 5$$
$$d^4(1,2) = \min\{d^3(1,2) = 3, \quad d^3(1,4) + d^3(4,3) = 2\} = 2$$
$$d^4(1,3) = \min\{d^3(1,3) = 5, \quad d^3(1,4) + d^3(4,3) = 2\} = 2$$

Complessità in Tempo

$$O(\substack{V\\text{iterate}} \cdot \substack{V^2\d^{()}(i,j)} \cdot \substack{c\\text {riempimento celle}}) = O(V^3) $$

Analogo Alla Moltiplicazione Di Matrici (Metodo Tropicale)

$d^{(l)} (i, j)$ = costo del cammino minimo di lunghezza $\leq l$

Il cammino minimo di lunghezza $l$ si trova estendendo il cammino di lunghezza $l-1$ con un nuovo arco

$$d^{(0)}(i, j) = \begin{cases} 0 & i=j\ +\infty &i \neq j \end{cases}$$ $$d^{(1)} = \begin{cases} 0 & i=j\ w(i, j) & (i, j) \in E\

• \infty & (i, j) \notin E \end{cases}$$ $$d^{(l)}(i,j) = \substack{\min \ 1 \leq z \leq n} {d^{(l-1)} (i, z) + w(z, j)}$$

title: Come ricostruire la soluzione?

Bisogna mantenere traccia dei predecessori

$$\Pi^{(l)}(i, j) = \text{valore di z che restituisce d(i,j)} = argmin (d^{(l)}(i,j))$$

Complessità Base

$$O(V^3) \cdot O(V) \implies O(V^4)$$

Fastest

$$d^l = d^{\frac l2} \cdot d^{\frac l2} \implies O(V^3\log V)$$

title: Algoritmo più veloce

Per calcolare i **cammini minimi tra tutte le coppie**, l'algoritmo più veloce rimane appicare [[#Dijkstra Con Heap]] V volte.

$$V (V \log V + E)$$

Algoritmo Di Johnson

[[#Bellman-Ford]] trova i cicli di costo negativo raggiungibili dalla sorgente, quelli non raggiungibili non vengono rilevati

SuperSource

Aggiungo un nodo $s$ chiamato supersource che è connesso a tutti gli altri vertici con archi di costo 0.

In sostanza è [[#Bellman-Ford]] con aggiunti $$E' = {(s,v) : \forall v \in V} $$ $$G' = {V \cup s, E \cup E'}$$

Se non esistono cicli di costo negativo $$ \hat w(i,j)= d(i) + w(i, j) - d(j) $$ $$ \hat w(i,j) > 0 $$ non altera il costo dei cicli, ma altera della stessa quantità ogni cammino $s \sim t$

Passaggi

• Costruisco G'
• Bellman-Ford(G')
• if not exist cicli negativi
  • ricalcolo i pesi $\hat w (i,j)$
  • $\forall v \in V$
    • Calcolo Dijkstra(G,v) $\implies \forall (i,j)\quad \hat d(i,j)$
    • Ricalcolo $d(i, j) = \hat d(i, j) - d(i) + d(j)$

Costo Passo 1

Costruisco G' $$G' = (V' + E')$$ $$|V'| = |V| + 1 = \Theta(V)$$ $$|E'| = |E| + |V| \leq q|E| = \Theta (E)$$

Costo Passo 2

Bellman-Ford (G')

$$|V'|\cdot|E'|=\Theta(V)\cdot\Theta(E)$$

Costo Passo 3

if not exist cicli negativi ricalcolo i pesi e eseguo dijkstra

$$\Theta(E) |V| ( V' \log V' + E')$$

Costo Passo 4

ricalcolo $d(i,j)$

$$\Theta(V^2)$$