3.4 Cammini minimi nei grafi aciclici¶
Parte 2 · Alberi e cammini · Capitolo 3 · Capitolo 3: Cammini minimi · Dispensa, volume 2 (PDF) · Slide · Esercizi: Cammini minimi · App: Cammini minimi: Dijkstra, Bellman–Ford, grafi aciclici
Definizione 3.13: grafo aciclico e ordine topologico
Un grafo orientato senza cicli orientati è un grafo aciclico orientato (DAG). Un ordine topologico di \(G=(N,A)\) è un ordinamento \(v_1,v_2,\dots,v_n\) dei suoi nodi tale che ogni arco va in avanti:
Proposizione 3.14: ordini topologici
Un grafo orientato ha un ordine topologico se e solo se è aciclico.
Dimostrazione
Se \(G\) ha un ordine topologico, un ciclo \(i_0,i_1,\dots,i_k=i_0\) andrebbe in avanti su ogni arco e tornerebbe al suo primo nodo: impossibile. Viceversa, sia \(G\) aciclico; ragioniamo per induzione su \(n\).
-
\(G\) ha un nodo senza archi entranti: altrimenti, camminando all'indietro lungo archi entranti a partire da un nodo qualsiasi, dopo \(n\) passi un nodo si ripete, e la passeggiata contiene un ciclo.
-
Mettiamo un nodo di questo tipo \(v_1\) per primo. Il grafo senza \(v_1\) è aciclico, e per induzione ha un ordine topologico \(v_2,\dots,v_n\); nessun arco entra in \(v_1\), quindi \(v_1,v_2,\dots,v_n\) è un ordine topologico di \(G\). □
Algoritmo: Cammini minimi in un grafo aciclico
STOP.Teorema 3.15: correttezza e tempo di esecuzione sui grafi aciclici
Su un grafo aciclico con lunghezze di qualsiasi segno, l'algoritmo «Cammini minimi in un grafo aciclico» termina con \(d(j)=\tilde{d}(j)\) per ogni \(j \in N\), e richiede tempo \(O(n+m)\).
Dimostrazione
Un grafo aciclico non ha alcun ciclo, quindi vale (A2). Ogni etichetta finita è la lunghezza di una passeggiata da \(s\), quindi \(d(j) \ge \tilde{d}(j)\) per il Lemma 3.3; le etichette possono solo diminuire.
-
Sia \(j\) raggiungibile e \(s=i_0,i_1,\dots,i_k=j\) un cammino minimo; i suoi nodi compaiono in quest'ordine nell'ordine topologico, perché ogni arco va in avanti.
-
Per induzione su \(t\), dopo l'elaborazione di \(i_t\) vale \(d(i_t) \le \tilde{d}(i_t)\): il cammino fino a \(i_{t-1}\) è minimo (Lemma 3.4), e l'elaborazione di \(i_{t-1}\) dà \(d(i_t) \le \tilde{d}(i_{t-1})+d_{i_{t-1}i_t}=\tilde{d}(i_t)\).
-
I nodi non raggiungibili da \(s\) conservano \(d(j)=+\infty=\tilde{d}(j)\).
Tempo. L'ordine topologico richiede tempo \(O(n+m)\) con un contatore degli archi entranti di ogni nodo, decrementato quando si toglie una coda; il Passo 1 esamina ogni arco una volta. □
-
La regola dell'indice minimo fissa un ordine per gli esempi; si può togliere qualsiasi nodo senza archi entranti.
-
Con le lunghezze \(-d_{ij}\) l'algoritmo calcola i cammini massimi, perché un grafo aciclico non ha cicli da ripetere. I cammini massimi nei grafi aciclici sono il cuore del Capitolo 9 «Gestione dei progetti».
Esempio 3.6: un'istanza aciclica
Invertendo l'arco \((4,3)\) del grafo di riferimento in \((3,4)\), con \(d_{34}=1\), si ottiene un grafo aciclico. Gli diamo le lunghezze dell'Esempio 3.1, tranne \(d_{54}=-3\) (in rosso).
Il Passo 0 dà l'ordine topologico \(1,3,2,5,4,6\): dopo \(1\), solo \(3\) non ha archi entranti; poi \(2\) e \(5\) sono liberi, e \(2\) va per primo. Ogni riga della tabella elabora un nodo e mostra le etichette dopo l'elaborazione:
| passo | nodo \(i\) | \(d(1)\) | \(d(2)\) | \(d(3)\) | \(d(4)\) | \(d(5)\) | \(d(6)\) |
|---|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(7\) | \(2\) | \(\infty\) | \(\infty\) | \(\infty\) |
| \(2\) | \(3\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(\infty\) |
| \(3\) | \(2\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(\infty\) |
| \(4\) | \(5\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(17\) |
| \(5\) | \(4\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(8\) |
| \(6\) | \(6\) | \(0\) | \(5\) | \(2\) | \(3\) | \(10\) | \(8\) |
I predecessori danno l'albero \((1,3)\), \((3,2)\), \((3,4)\), \((3,5)\), \((4,6)\) (in blu). L'arco negativo \((5,4)\) non viene usato: \(d(5)-3=7>3=d(4)\). Con le lunghezze \(-d_{ij}\) le lunghezze dei cammini massimi da \(1\) sono \((0,7,2,10,10,17)\).
Un grafo è aciclico se e solo se ha un ordine topologico. Esaminando i nodi in quest'ordine, ogni etichetta è definitiva quando il suo nodo viene elaborato: cammini minimi in tempo \(O(n+m)\), con lunghezze di qualsiasi segno.
Avanti: 3.5 L'algoritmo di Bellman–Ford