Module: Algoritmo de Ford-Bellman


Problem

1/6

Ford-Bellman: O Começo (C++)

Theory Click to read/hide

Algoritmo de Ford-Bellman
Vamos receber um grafo ponderado direcionado G com n vértices e m arestas, e algum vértice inicial v . É necessário encontrar os comprimentos dos caminhos mais curtos do vértice v para todos os outros vértices.

Como Dijkstra, Ford-Bellman procura a distância do vértice 1 a todos os outros, mas trabalha com arestas negativas forte>.
 
O próprio algoritmo de Ford-Bellman consiste em várias fases (n-1). A cada fase, todas as arestas do grafo são examinadas, e o algoritmo tenta relaxar ao longo de cada aresta (a, b) do custo c. Relaxamento ao longo de uma borda — esta é uma tentativa de melhorar o significado de d[a]  o valor d[b] + c. Na verdade, isso significa que estamos tentando melhorar a resposta para o vértice usando a aresta  e a resposta atual para o topo.

O array d é um array dos menores comprimentos do vértice inicial, assim como em Dijkstra, inicialmente o preenchemos com os maiores números possíveis, exceto para o vértice inicial, no qual você precisa colocar 0.
Para armazenar arestas, não é utilizada uma matriz de adjacência ou uma matriz de peso, mas uma lista que indica de qual nó a aresta sai (from), para onde ela vem (to) e seu peso (custo).
  borda da estrutura { int de, para, custo; }; vetor<borda> arestas;
A constante INF denota o número "infinito" - deve ser escolhido de forma que obviamente exceda todos os comprimentos de caminho possíveis.

A implementação mais simples do algoritmo: d[v] = 0; for (int i=0; i<n-1; ++i) para (int j=0; j<m; ++j)      if (d[bordas[j].de] <INF)        d[bordas[j].to] = min(d[bordas[j].to], d[bordas[j].de] + arestas[j].custo);

ou um pouco mais curto usando a sintaxe C++11:
  d[v] = 0; for (int i=0; i< n-1; ++i) para (aresta j: arestas) if (d[j.from] <INF) d[j.to] = min(d[j.to], d[j.de] + j.custo);

Exemplo de trabalho


Pegue um gráfico direcionado simples  com 5 nós, 4 arestas com peso igual a 1.

Vamos apresentar uma lista de arestas nessa ordem.
4 5 1
3 4 1
2 3 1
1 2 1

Valores iniciais na matriz de comprimentos mais curtos:
 
0 inf inf inf inf

onde inf deve ser um inteiro correspondente que é sempre maior que o peso da aresta.

Após a 1ª passagem
 
0 1 inf inf inf

Após a 2ª passagem
 
0 1 2 inf inf

Após a 3ª passagem
 
0 1 2 3 inf


Após a 4ª passagem
 
0 1 2 3 4

Se alimentarmos as arestas de 1 a 1, poderemos encontrar os comprimentos mais curtos após a 1ª passagem.

 

Problem

Complete o programa para que resolva corretamente o seguinte problema.

Dado um grafo direcionado que pode ter múltiplas arestas e loops. Cada aresta tem um peso expresso como um número inteiro (possivelmente negativo). É garantido que não há ciclos de peso negativo.
Você precisa calcular os comprimentos dos caminhos mais curtos do vértice número 1 para todos os outros vértices.
 
Entrada
O programa primeiro recebe o número N (1 <= N <= 100) – o número de vértices do gráfico e o número M (0 <= M <= 10000) – número de costelas. As linhas a seguir contêm M de triplos de números que descrevem as arestas: o início da aresta, o fim da aresta e o peso (peso – é um número inteiro de -100 a 100).< /div>
 
Saída
O programa deve gerar N números – distâncias do vértice número 1 a todos os vértices do grafo. Se não houver caminho para o vértice correspondente, imprima o número 30000 em vez do comprimento do caminho.
 
Exemplos
# Entrada Saída
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 

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++
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!