Algoritmo de Bellman-Ford
O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um digrafo (grafo orientado ou dirigido) ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, num tempo menor, porém exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de Bellman-Ford é normalmente usado apenas quando existem arestas de peso negativo.[1]
O algoritmo de Bellman-Ford executa em tempo onde V é o número de vértices e E o número de arestas.[2][3]
Pseudocódigo editar
Assim como o algoritmo de Dijkstra, o algoritmo de Bellman-Ford utiliza a técnica de relaxamento, ou seja, realiza sucessivas aproximações das distâncias até finalmente chegar na solução. A principal diferença entre Dijkstra e Bellman-Ford é que no algoritmo de Dijkstra é utilizada uma fila de prioridades para selecionar os vértices a serem relaxados, enquanto o algoritmo de Bellman-Ford simplesmente relaxa todas as arestas.
Bellman_Ford(G,pesos,inicial)
para todo vertice ∈ V
λ[vertice] ← ∞
π[vertice] ← nulo
λ[inicial] ← 0
para i de 1 até |V| -1
para toda aresta = (u,v) ∈ A
se λ[v] > λ[u] + pesos(u,v) # relaxamento
λ[v] ← λ[u] + pesos(u,v)
π[v] ← u
G é um grafo no formato G = (V,A), π[v] indica o predecessor de v, λ[v] é o custo de sair da origem e chegar até o vértice v e inicial é o vértice inicial. Após o término do algoritmo, para cada v pertencente aos vértices de G, π[v] → y representa uma aresta selecionada para a árvore geradora mínima (se y ≠ nulo) e, pensando em árvore, λ[v] representa a distância da raiz até o vértice v.
Exemplo de código editar
C++ editar
#include <iostream>
#include <vector>
#include <array>
#include <climits> // INT_MAX
using namespace std;
struct Node {
int p = -1;
int d = INT_MAX;
};
using edges_t = vector<array<int, 2>>;
using graph_t = vector<edges_t>;
// if a function of this type returns true, graph traversal will be interrupted
using edge_cb = bool(*)(vector<Node>&, int, int, int);
inline bool isNegativeCycle(vector<Node>& nodes, int u, int v, int w) {
return nodes[v].d > nodes[u].d + w;
}
inline bool relaxNode(vector<Node>& nodes, int u, int v, int w) {
// Relaxation
if (nodes[v].d > nodes[u].d + w) {
nodes[v].d = nodes[u].d + w;
nodes[v].p = u;
}
return false;
}
// returns true if the traversal was successful
bool traverseAllEdges(const graph_t& graph, vector<Node>& nodes, edge_cb cb) {
for (int u = 0; u < graph.size(); ++u) {
const edges_t adjacent = graph[u];
for (const auto& edge : adjacent) {
int v = edge[0]; // Adjacent vertex
int w = edge[1]; // Weight
if (cb(nodes, u, v, w)) return false;
}
}
return true;
}
bool bellmanFord(const graph_t& graph, int src, int dst, vector<int>& path) {
const int len = graph.size();
vector<Node> nodes(len);
// Initialization
for (int i = 0; i < len; ++i) {
nodes[i] = Node();
}
nodes[src].d = 0;
for (int i = 0; i < len; ++i) {
traverseAllEdges(graph, nodes, relaxNode);
}
// Check for negative-weight cycles
// Stop, if such cycles were detected
if (!traverseAllEdges(graph, nodes, isNegativeCycle)) return false;
// Construct the path from src to dst
path.push_back(dst);
Node node = nodes[dst];
while (node.p != -1) {
path.insert(path.begin(), node.p);
node = nodes[node.p];
}
return true;
}
int main() {
graph_t graph(5, edges_t(3));
graph[0] = {{1, 6}, {3, 7}};
graph[1] = {{2, 5}, {3, 8}, {4, -4}};
graph[2] = {{1, -2}};
graph[3] = {{2, -3}, {4, 9}};
graph[4] = {{0, 2}, {2, 7}};
vector<int> path;
if (bellmanFord(graph, 0, 2, path)) {
for (const int& v : path) {
cout << v << ' ';
}
} else {
cout << "negative cycle detected\n";
}
}
Ver também editar
Referências
- ↑ Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein (2007). Algorithmen – Eine Einführung 2. ed. München: Oldenbourg Wissenschaftsverlag. pp. 585–586. ISBN 978-3-486-58262-8
- ↑ RFC 1058
- ↑ [1]
- ↑ https://gist.github.com/alexnoz/3f96d821481b2879ba7b683501d2d8d1
Ligações externas editar
- «Código C++» (em inglês)
