Introduzione
Per effettuare una ricerca dei cammini minimi in un grafo con pesi negativi dobbiamo assicuraci che non esistano cicli con peso totale negativo all interno del grafo.
Ciclo Negativo
Un ciclo negativo è un ciclo diretto in un grafo in cui la somma dei pesi degli archi che lo compongono è negativa.
Il ciclo in figura ha costo:
5-3-6+3-2 = -2
Problema
Se in un cammino tra i nodi
s
et
è presente un nodo appartiene ad un ciclo negativo, allora non esiste il cammino di costo minimo tras
et
.
Questo perché per il ciclo
W
si hacosto(W) < 0
, ripassando più volte attraverso il cicloW
possiamo abbassare arbitrariamente il costo del cammino das
at
.
Proprietà
Se il grafo
G
non contiene cicli negativi, allora per ogni nodot
raggiungibile dalla sorgentes
esiste un cammino di costo minimo che attraversa al piùn-1
archi.Questo perché un cammino minimo non percorre mai un nodo più di una volta.
Quindi: Questo garantisce che il costo minimo può essere calcolato considerando solo cammini di questa lunghezza.
Algoritmo di Bellman - Ford
Se il grafo G
non contiene cicli negativi, allora per ogni nodo t
raggiungibile dalla sorgente s
esiste un cammino di costo minimo che attraversa al più n - 1
archi.
Per l’algoritmo definiamo quindi la seguente tabella T
di dimensione n x n
dove:
T[i][j]
= costo di un cammino minimo das
al nodoj
di lunghezza al piùi
.
In particolare la prima riga avrà tutti ad eccezione della sorgente cha ha valore 0
.
Per calcolare i valori delle altre righe dobbiamo distinguere due casi:
Caso 1:
Se il costo per raggiungere
j
ha lunghezza inferiore o uguale al valorei
allora prendiamo il valore precedente della tabella, quindiT[i][j] = T[i][j - 1]
.
Caso 2:
Se caso 1 è falso allora deve esistere un cammino minimo di lunghezza più
i - 1
ad un nodox
il quale poi tramite un arco ci porterà aj
.Dobbiamo quindi prendere il cammino minimo fra tutti questi cammini che ci portano dalla sorgente ad un
x
e dax
aj
tramite un solo arco, ovvero:
Ovviamente non sappiamo in quale dei due casi ci troviamo e quindi prendiamo il minore fra questi due casi:
La soluzione al nostro problema sarà all’ultima riga.
Calcolo Costo Cammini Minimi
Implementiamo un algoritmo per il calcolo il costo del cammini minimi, che calcola il costo del cammino minimo che parte da un nodo s
e raggiunge ogni nodo del grafo.
def CostoCammini(G, s):
n = len(G)
T = [[float('inf')] * n for _ in range(n)]
T[0][s] = 0
GT = Trasposto(G)
for i in range(1, n):
for j in range(n):
T[i][j] = T[i - 1][j]
if j != s:
for x, costo in GT[j]:
T[i][j] = min(T[i][j], T[i-1][x] + costo)
return T[n-1]
def Trasposto(G):
GT = [[] for _ in G]
for i in range(len(G)):
for j, costo in G[i]:
GT[j].append((i, costo))
return GT
Per migliorare l’efficenza e per conoscere gli archi entranti al nodo j
, conviene calcolare il grafo trasposto GT
di G
, in questo modo in GT[j]
avremo tutti i nodi x
tali che in G
esiste l’arco x -> j
.
Costo
- La tabella costa .
- Calcolare il trasposto
- I due
for
più interni in realtà scorrono le liste di adiacenza dei nodi quindi hanno un costo totale di mentre quello esterno . In totale i 3 for costanoQuindi il costo totale è di
Calcolo Cammini Minimi
Precedentemente abbiamo calcolato il costo per raggiungere i nodi ora ci interessa trovare anche i nodi da percorrere per effettuare qui cammini, dobbiamo quindi modificare l’algoritmo in modo che ci restituisca il vettore dei padri.
Per fare ciò dobbiamo mantenere per ogni nodo j
il suo predecessore P[j]
, questo valor andrà aggiornato ogni volta che il valore T[k][j]
cambia, ovvero quanto un nuovo percorso minore è stato trovato.
def CostoCammini(G, s):
n = len(G)
T = [[float('inf')] * n for _ in range(n)]
T[0][s] = 0
P = [-1] * n
P[s] = s
GT = Trasposto(G)
for k in range(1, n):
for j in range(n):
if j == s:
T[k][j] = 0
else:
for x, costo in GT[j]:
if T[k-1][x] + costo < T[k][j]:
T[k][j]=T[j-1][x] + costo
P[i] = x
return T[n-1], P
Ottimizzazioni
Proprietà Tabella:
- Se notiamo che una riga è uguale alla precedente allora anche le righe successive non cambieranno, possiamo quindi terminare l’algoritmo.
- Non serve avere sempre in memoria l’intera tabella, ci basta l’ultima riga e la precedente. In questo modo riduciamo la complessità di spazio da a .
Rilevamento Cicli Negativi:
- Questo algoritmo non si accorge se ci sono o no cicli negativi, se vogliamo però effettuare un test, ci basta calcolare i percorsi fino a distanza
n
, aggiungendo quindi una riga.- Le ultime due righe
n−1
en
saranno uguali se e solo se nel grafo non ci sono cicli negativi raggiungibili das
. Implementare il test non cambia l’asintotica dell’algoritmo.