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.

O algoritmo de Bellman-Ford executa em tempo $O(V\times E)$ onde V é o número de vértices e E o número de arestas.

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";

  }

}

Ver também

• Teoria dos grafos
• Problema do caminho mínimo
• Algoritmo de Dijkstra

Ligações externas

• «Código C++» (em English)