Cammini minimi e algoritmo di Dijkstra

Definizione (lunghezza di un cammino e distanza). Sia $G = (V, E, w)$ un grafo non diretto e pesato, con $w : E \to \mathbb{R}$ (esempio: rete di aeroporti con distanze in km; $\mathbb{R}$ sono i numeri reali: Insiemi numerici (N, Z, Q, R)Naturali, interi, razionali e reali, perché la radice di 2 obbliga a passare da Q a R, e gli intervalli.Insiemi numerici (N, Z, Q, R) →). Il problema è lo stesso dell'instradamento dei pacchetti in Internet, dove i pesi sono costi dei collegamenti e l'algoritmo è detto link state (Algoritmi di instradamento - link state e distance vectorL'instradamento (routing) trova il percorso di costo minimo in un grafo pesato in cui i router sono nodi e le reti tra due router sono archi. Link state: ogni router diffonde con un flooding i pacchetti LSP sui propri collegamenti, ricostruisce tutto il grafo e applica Dijkstra (nodi con stato (distanza, permanente o temporaneo)). Distance vector: ogni router conosce solo i vicini e scambia con loro il proprio vettore delle distanze, aggiornato con Bellman-Ford $D_{A,w}=\min{D_{A,w},,D_{A,Y}+d_{Y,w}}$; converge in al più $n-1$ giri ma può soffrire del conteggio all'infinito (limite a 16, hold down, aggiornamenti immediati, split horizon con poison reverse). Path vector: ogni annuncio porta l'intero cammino, si sceglie per politica e non per costo, e i cicli si scoprono trovando sé stessi nel cammino. Dijkstra è corretto se i costi sono non negativi (invariante: un nodo permanente ha già la distanza vera); Bellman-Ford è corretto perché dopo $k$ giri conosce i cammini minimi con al più $k+1$ archi.Algoritmi di instradamento - link state e distance vector →, Instradamento e inoltroL'inoltro (forwarding) mette il pacchetto sulla strada verso la destinazione, un salto alla volta (hop by hop). Se la destinazione è nella stessa rete del mittente l'inoltro è diretto (si usa l'ARP per il MAC del destinatario), altrimenti è indiretto: il pacchetto va al router successivo (next hop) indicato dalla tabella di instradamento, o al default gateway. Con le netmask: l'inoltro è diretto attraverso l'interfaccia $x$ se $\text{IP(dst)}\ \text{AND}\ \text{NM}(x)=\text{IP}(x)\ \text{AND}\ \text{NM}(x)$; altrimenti si scorre la tabella dalla maschera più lunga (longest prefix match) e si usa il primo match. La riga con rete $0.0.0.0$ e maschera $0.0.0.0$ (default route) corrisponde sempre. L'aggregazione di rotte (route aggregation) riduce la tabella, e nell'inoltro con etichette (MPLS) la tabella si consulta per indice.Instradamento e inoltro →). La lunghezza di un cammino $u_1, \dots, u_k$ è $\sum_{i=1}^{k-1} w(u_i, u_{i+1})$; se $w(e) = 1$ per ogni arco è il numero di archi. La distanza $d(u, v)$ è la minima lunghezza di un cammino da $u$ a $v$ e il cammino che la realizza è un cammino minimo.

Esempio. Nel grafo dell'esempio svolto il cammino $A,C,F,E$ ha lunghezza $9+2+9=20$ e $d(A,E)=20$.

Proposizione (sottostruttura ottima dei cammini minimi). Se $u_1, \dots, u_k$ è un cammino minimo da $u_1$ a $u_k$, allora $u_i, \dots, u_j$ è un cammino minimo da $u_i$ a $u_j$ per ogni $1 \le i < j \le k$. Dimostrazione (per assurdo: Tecniche di dimostrazioneDimostrazione diretta, per contronominale e per assurdo di un teorema del tipo ipotesi implica tesi.Tecniche di dimostrazione →): se esistesse un cammino più corto da $u_i$ a $u_j$, sostituendolo nel cammino originale si otterrebbe un cammino da $u_1$ a $u_k$ più corto, contro l'ipotesi. In formule: la lunghezza del cammino originale è $\ell(u_1..u_i)+\ell(u_i..u_j)+\ell(u_j..u_k)$; sostituendo il termine centrale con uno strettamente minore si ottiene una somma strettamente minore.

Esempio. Se $A,C,F,E$ è un cammino minimo da $A$ a $E$, allora $C,F$ è un cammino minimo da $C$ a $F$ ($d(C,F)=2$).

SSSP (single-source shortest paths): dato $s \in V$, determinare le distanze da $s$ a tutti gli altri vertici e i relativi cammini minimi (rappresentati dai campi parent). Si assume che $G$ non abbia cicli di peso negativo (altrimenti la lunghezza potrebbe diventare arbitrariamente piccola). Se tutti i pesi sono $1$ basta la BFS in $\Theta(n + m)$ (vedi Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →).

Algoritmo di Dijkstra

Definizione (algoritmo di Dijkstra). Sviluppato nel 1956, richiede pesi non negativi. Generalizza la BFS: a partire da $s$ fa crescere una cloud di vertici di cui si conoscono già distanza da $s$ e cammino minimo.

Esempio. Sul grafo dell'esempio svolto Dijkstra da $A$ estrae i vertici in ordine di distanza: $A\,(0)$, $B\,(7)$, $C\,(9)$, $F\,(11)$, $D\,(20)$, $E\,(20)$.

La stessa idea della BFS (esplorare per "cerchi" crescenti attorno a $s$) vale qui con una differenza: nella BFS i cerchi sono i livelli $L_i$ (distanza in archi, Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →); con i pesi bisogna estrarre ogni volta il vertice di distanza corrente minima, e per questo serve una coda con priorità al posto della coda FIFO.

• La cloud parte con $\{s\}$.
• Ogni vertice $v$ ha v.D = distanza corrente da $s$ (lunghezza del miglior cammino noto con vertici interni nella cloud) e v.parent = predecessore su quel cammino.
• A ogni iterazione entra nella cloud il vertice $u$ esterno con D minimo; poi si rilassano gli archi $(u, v)$ con $v$ ancora fuori: se u.D + w(u,v) < v.D si pone v.D <- u.D + w(u,v) e v.parent <- u.
• I vertici fuori dalla cloud stanno in una coda con priorità $Q$ con chiave v.D (vedi Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →).

Algoritmo ShortestPaths(G, s)
Input: grafo non diretto G=(V,E,w), pesi >= 0, sorgente s
Output: distanze e cammini minimi da s, nei campi v.D e v.parent
s.D <- 0; s.parent <- null
forall v in V - {s} do v.D <- +infinito; v.parent <- null
Q <- coda con priorità con tutti i vertici (chiave v.D)
while Q non è vuota do
    u <- Q.removeMin()
    forall (u, v) in E con v in Q do
        if u.D + w(u,v) < v.D then
            v.D <- u.D + w(u,v); v.parent <- u
            aggiorna Q per la nuova chiave di v

Esempio svolto

Vertici $A..F$ e archi (peso): $AB\,(7)$, $AC\,(9)$, $AF\,(14)$, $BC\,(10)$, $BD\,(15)$, $CD\,(11)$, $CF\,(2)$, $DE\,(6)$, $EF\,(9)$. Sorgente $A$.

Distanze da $A$: $B = 7$, $C = 9$, $F = 11$, $D = 20$, $E = 20$. Cammini (da parent): $B \leftarrow A$; $C \leftarrow A$; $F \leftarrow C$; $D \leftarrow C$; $E \leftarrow F$. Quindi il cammino minimo $A \to E$ è $A, C, F, E$ di lunghezza $9 + 2 + 9 = 20$. Si noti che il cammino con meno archi verso $D$, cioè $A,B,D$ di lunghezza $22$, non è il minimo: $A,C,D$ vale $9+11=20$. Il cammino con il minor numero di archi (BFS) e quello di peso minimo sono in generale diversi. Controllo dei rilassamenti dell'iterazione 2: da $C$ (distanza $9$) l'arco $CD$ dà $9+11=20<22$, aggiorna $D$ e il suo parent da $B$ a $C$; l'arco $CF$ dà $9+2=11<14$, aggiorna $F$ da $A$ a $C$; l'arco $CB$ non si rilassa perché $B$ è già in cloud. (Verificato eseguendo un'implementazione con heap; a parità $D$ e $E$ entrano in cloud in uno dei due ordini.)

Correttezza

Segue da due lemmi (la dimostrazione del Lemma 2 non è richiesta nel dettaglio). Alla fine di ogni iterazione del while, per ogni $v \in V$:

• Lemma 1. Se v.D $= +\infty$ allora v.parent $=$ null; se v.D $< +\infty$, il cammino ottenuto risalendo da $v$ con parent è un cammino da $s$ a $v$ di lunghezza v.D.
• Lemma 2. Quando $u$ viene estratto da $Q$, u.D $= d(s, u)$.

Idea per il Lemma 2. Se per assurdo u.D $> d(s,u)$, si considera un cammino minimo da $s$ a $u$ e il primo vertice $z$ fuori dalla cloud su di esso. Il predecessore di $z$ è in cloud, quindi l'arco verso $z$ è stato rilassato e z.D $\le d(s,z) \le d(s,u) <$ u.D (qui servono i pesi $\ge 0$: $d(s,z) \le d(s,u)$). Allora $z$ sarebbe stato estratto prima di $u$, contraddizione. Perché z.D $\le d(s,z)$: il cammino minimo da $s$ a $z$ ha come ultimo arco quello dal predecessore $y$ in cloud; per il Lemma 2 applicato a $y$ si ha y.D $=d(s,y)$, e il rilassamento di $(y,z)$ ha posto z.D $\le$ y.D $+w(y,z)=d(s,z)$ (sottostruttura ottima). Perché $d(s,z)\le d(s,u)$: $z$ sta sul cammino minimo prima di $u$ e i pesi dopo di lui sono $\ge0$, quindi la distanza non può diminuire proseguendo. Con un peso negativo questa seconda disuguaglianza cade, ed è esattamente il punto che si rompe nell'esempio seguente.

Perché servono pesi non negativi. In un grafo diretto con archi $s \to a$ di peso $2$, $s \to b$ di peso $3$ e $b \to a$ di peso $-2$ (nessun ciclo negativo) Dijkstra estrae $a$ con $D = 2$, ma il cammino $s, b, a$ vale $1$. Passo per passo: si estrae $s$ ($D=0$) e si rilassano $a$ ($D=2$) e $b$ ($D=3$); il minimo in $Q$ è $a$ con $D=2$, che entra in cloud e non viene più aggiornato; si estrae $b$ ($D=3$) e si controlla $b\to a$, ma $a$ non è più in $Q$ e il rilassamento viene saltato: l'algoritmo termina con $D(a)=2$ invece di $1$. (In un grafo non diretto un solo arco negativo è già un ciclo negativo: si percorre avanti e indietro.)

Complessità

Dipende dall'implementazione della coda $Q$. Ogni vertice è estratto una volta ($n$ removeMin), si fanno al più $m$ aggiornamenti di chiave (un rilassamento per arco: l'arco $(u,v)$ è rilassato quando viene estratto il primo dei suoi due estremi, perché all'estrazione del secondo il primo è già fuori da $Q$), e ogni vertice mantiene un puntatore alla propria entry in $Q$ (altrimenti trovare l'entry da aggiornare costerebbe una ricerca; è l'idea delle posizioni di Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →). Le operazioni sullo heap sono quelle di HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap → e la costruzione iniziale è lineare (Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →).

Nello heap l'aggiornamento di una chiave diminuita richiede un up-heap bubbling in $O(\log n)$ (vedi HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →). Totale:

• heap: $n \cdot \Theta(\log n) + m \cdot \Theta(\log n) + \Theta(n + m) = O((n + m) \log n)$;
• lista non ordinata: $n \cdot \Theta(n) + m \cdot \Theta(1) = O(n^2 + m) = O(n^2)$ (perché $m \le n^2$).

Teorema (complessità dell'algoritmo di Dijkstra). La complessità di ShortestPaths(G, s) è $O(\min\{n^2, (n + m) \log n\})$: con la scelta migliore dell'implementazione. Per grafi sparsi ($m = O(n)$) conviene lo heap ($O(n \log n)$); per grafi densi ($m = \Theta(n^2)$) la lista ($\Theta(n^2)$ contro $\Theta(n^2 \log n)$).

Esempio. Con $n=1000$ e $m=3000$ conviene lo heap: $(n+m)\log_2n\approx4\cdot10^4$ contro $n^2=10^6$ ($\log_2 1000\approx 9{,}97$, quindi $4000\cdot9{,}97\approx39\,900$).

Il grafico fissa $n=1000$ e fa variare $m$: la curva dello heap cresce linearmente con $m$, quella della lista è costante. Si incontrano a $(1000+m)\cdot 9{,}97 = 10^6$, cioè $m\approx 99\,000\approx n^2/10$: sopra questo valore (grafi molto densi, in cui $m$ è una frazione consistente del massimo $\frac{n(n-1)}{2}\approx 500\,000$) conviene la lista non ordinata; sotto (grafi sparsi) lo heap. Le costanti sono ignorate, quindi il punto di incrocio è indicativo (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →).

Errori comuni

• Usare Dijkstra con pesi negativi.
• Dimenticare l'aggiornamento di parent quando si migliora D (si ottengono le distanze ma non i cammini).
• Rilassare anche archi verso vertici già nella cloud (inutile, non cambia la distanza finale).
• Dire che costa sempre $O(m \log n)$: dipende dall'implementazione di $Q$; $O(n \log n)$ non tiene conto degli aggiornamenti di chiave su un grafo denso.