Algoritmo Ford-Bellman
Démosle un gráfico ponderado dirigido G con n vértices y m aristas, y algunos vértices iniciales v . Se requiere encontrar las longitudes de los caminos más cortos desde el vértice v a todos los demás vértices.
Al igual que Dijkstra, Ford-Bellman busca la distancia desde el vértice 1 a todos los demás, pero funciona con bordes negativos< / fuerte>.
El propio algoritmo Ford-Bellman consta de varias fases ( n-1). En cada fase, se examinan todos los bordes del gráfico y el algoritmo intenta relajarse a lo largo de cada borde (a, b) del costo c. Relajación a lo largo de un borde — este es un intento de mejorar el significado de d[a] el valor d[b] + c. De hecho, esto significa que estamos tratando de mejorar la respuesta para el vértice usando el borde y la respuesta actual para la parte superior.
La matriz d es una matriz de las longitudes más cortas desde el vértice inicial, al igual que en Dijkstra, inicialmente la llenamos con números tan grandes como sea posible, excepto el vértice inicial, en el que debe colocar 0.
Para almacenar aristas no se utiliza una matriz de adyacencia ni una matriz de pesos, sino una lista que indica de qué nodo sale la arista ( from), a cuál llega ( to) y su peso (cost).
borde de la estructura {
int desde, hasta, costo;
};
vector<borde> bordes;
La constante INF denota el número "infinito" - debe elegirse de tal manera que exceda obviamente todas las longitudes de ruta posibles.
La implementación más simple del algoritmo:
d[v] = 0;
para (int i=0; i<n-1; ++i)
para (int j=0; j<m; ++j)
if (d[bordes[j].desde] <INF)
d[aristas[j].a] = min(d[aristas[j].a], d[aristas[j].desde] + aristas[j].costo);
o un poco más corto usando la sintaxis C++11:
d[v] = 0;
para (int i=0; i< n-1; ++i)
para (borde j: bordes)
si (d[j.de] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.cost);
Ejemplo de trabajo
Tome un gráfico dirigido simple con 5 nodos, 4 aristas con peso igual a 1.
Presentemos una lista de aristas en ese orden.
4 5 1
3 4 1
2 3 1
1 2 1
Valores iniciales en matriz de longitudes más cortas:
| 0 |
inf |
inf |
inf |
inf |
donde inf debe ser un entero coincidente que siempre es mayor que el peso del borde.
Después del primer pase
| 0 |
1 |
inf |
inf |
inf |
Después del segundo pase
| 0 |
1 |
2 |
inf |
inf |
Después del tercer pase
| 0 |
1 |
2 |
3 |
inf |
Después del 4to pase
| 0 |
1 |
2 |
3 |
4 |
Si alimentamos los bordes en orden del 1 al último, podríamos encontrar las longitudes más cortas después de la primera pasada.
|