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:
onde inf deve ser um inteiro correspondente que é sempre maior que o peso da aresta.
Após a 1ª passagem
Após a 2ª passagem
Após a 3ª passagem
Após a 4ª passagem
Se alimentarmos as arestas de 1 a 1, poderemos encontrar os comprimentos mais curtos após a 1ª passagem.
|