Cammini minimi e algoritmo di Dijkstra

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). 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.

Proposizione (sottostruttura ottima). 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: 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.

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

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.

• 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$. (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é 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$. (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), e ogni vertice mantiene un puntatore alla propria entry in $Q$.

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. 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)$).

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.