Algoritmo Ford-Bellman
Diamo un grafo pesato diretto G con n vertici e m archi, e alcuni vertici iniziali v . È necessario trovare le lunghezze dei percorsi più brevi dal vertice v a tutti gli altri vertici.
Come Dijkstra, Ford-Bellman cerca la distanza dal vertice 1 a tutti gli altri, ma lavora con bordi negativi< / forte>.
L'algoritmo Ford-Bellman stesso consiste in diverse fasi ( n-1). Ad ogni fase, vengono esaminati tutti gli archi del grafo e l'algoritmo cerca di rilassarsi lungo ogni arco (a, b) del costo c. Relax lungo un bordo — questo è un tentativo di migliorare il significato di d[a] il valore d[b] + c. In effetti, questo significa che stiamo cercando di migliorare la risposta per il vertice utilizzando il bordo e la risposta corrente per la parte superiore.
L'array d è un array delle lunghezze più brevi dal vertice iniziale, proprio come in Dijkstra, inizialmente lo riempiamo con i numeri più grandi possibili, ad eccezione del vertice iniziale, in cui devi inserire 0.
Per memorizzare gli spigoli non viene utilizzata una matrice di adiacenza o una matrice di peso, ma una lista che indica da quale nodo parte lo spigolo ( from), a quale arriva ( to) e il suo peso (cost).
struct bordo {
int da, a, costo;
};
vettore<bordo> bordi;
La costante INF denota il numero "infinito" - deve essere scelto in modo tale da superare ovviamente tutte le possibili lunghezze di percorso.
L'implementazione più semplice dell'algoritmo:
d[v] = 0;
per (int i=0; i<n-1; ++i)
for (int j=0; j<m; ++j)
if (d[edge[j].from] <INF)
d[bordi[j].to] = min(d[bordi[j].to], d[bordi[j].da] + bordi[j].cost);
o un po' più breve usando la sintassi C++11:
d[v] = 0;
per (int i=0; i< n-1; ++i)
per (bordo j: bordi)
if (d[j.from] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.cost);
Esempio di lavoro
Prendi un semplice grafico diretto con 5 nodi, 4 spigoli con peso pari a 1.
Introduciamo un elenco di spigoli in quest'ordine.
4 5 1
3 4 1
2 3 1
1 2 1
Valori iniziali nell'array di lunghezze minime:
dove inf dovrebbe essere un numero intero corrispondente che è sempre maggiore del peso del bordo.
Dopo il 1° passaggio
Dopo il 2° passaggio
Dopo il 3° passaggio
Dopo il 4° passaggio
Se inseriamo i bordi nell'ordine dall'1 all'ultimo, potremmo trovare le lunghezze più corte dopo la prima passata.
|