Module: Algoritmo de Ford-Bellman


Problem

1/6

Ford-Bellman: El comienzo (C++)

Theory Click to read/hide

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:
 
donde inf debe ser un entero coincidente que siempre es mayor que el peso del borde.

Después del primer pase
 
0 inf inf inf inf

Después del segundo pase
 
0 1 inf inf inf

Después del tercer pase
 
0 1 2 inf inf


Después del 4to pase
 
0 1 2 3 inf

Si alimentamos los bordes en orden del 1 al último, podríamos encontrar las longitudes más cortas después de la primera pasada.

 

Problem

Complete el programa para que resuelva correctamente el siguiente problema.

Dado un gráfico dirigido que puede tener múltiples aristas y bucles. Cada borde tiene un peso expresado como un número entero (posiblemente negativo). Se garantiza que no hay ciclos de peso negativos.
Debe calcular las longitudes de los caminos más cortos desde el vértice número 1 hasta todos los demás vértices.
 
Entrada
El programa primero recibe el número N (1 <= N <= 100) – el número de vértices del gráfico y el número M (0 <= M <= 10000) – número de costillas. Las siguientes líneas contienen M de triples de números que describen los bordes: el comienzo del borde, el final del borde y el peso (el peso es un número entero de -100 a 100).< /div>
 
Salida
El programa debe generar números N – distancias del vértice número 1 a todos los vértices del gráfico. Si no hay ruta al vértice correspondiente, imprima el número 30000 en lugar de la longitud de la ruta.
 
Ejemplos
0 1 2 3 4

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Entrada Salida
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {         
    }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!