Vai al contenuto

3.4 Cammini minimi nei 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:

\[ (v_a,v_b) \in A \quad \Longrightarrow \quad a<b . \]

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

  1. \(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.

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

Input: un grafo aciclico \(G=(N,A)\) con lunghezze \(d_{ij}\) di qualsiasi segno, una sorgente \(s \in N\)
Output: le distanze \(d(j)=\tilde{d}(j)\) e i predecessori \(\mathit{pred}(j)\)
1Passo 0 (ordine). Trovare un ordine topologico: togliere ripetutamente un nodo senza archi entranti (quello di indice minimo, se ce n'è più di uno).
2 Porre \(d(s):=0\) e \(d(j):=+\infty\) per \(j \neq s\).
3Passo 1 (etichette). Per ogni nodo \(i\) in ordine topologico con \(d(i)<+\infty\), e per ogni arco \((i,j) \in \delta^+(i)\):
4 se \(d(i)+d_{ij}<d(j)\), porre \(d(j):=d(i)+d_{ij}\) e \(\mathit{pred}(j):=i\).
5 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.

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

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

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

Figura 3

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