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
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
C++
#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"; } }
[4]
Ver também
- Teoria dos grafos
- Problema do caminho mínimo
- Algoritmo de Dijkstra
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 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ RFC 1058
- ↑ [1]
- ↑ https://gist.github.com/alexnoz/3f96d821481b2879ba7b683501d2d8d1
Ligações externas
- «Código C++» (em inglês)
Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|
- Portal das tecnologias de informação
- Portal da matemática