Algoritmo de Bellman-Ford

O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um dígrafo ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, em um 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 a)$ onde v é o número de vértices e a o número de arestas.

Pseudocódigo

função BellmanFord(lista vértices, lista arestas, vértice origem)
   // Esta implementação recebe um grafo representado como uma
   // lista de vértices e arestas e modifica os vértices para
   // que que seus atributos distância e anterior armazenem 
   // os caminhos mais curtos.

   // Passo 1: Inicializar o grafo
   para cada vértice v em vértices faça:
       se v é origem então:
           v.distância = 0
       senão:
           v.distância := infinito
       v.anterior := nulo
   
   // Passo 2: Ajustar as arestas repetidamente
   repita tamanho (vértices) vezes:
       para cada aresta uv em arestas faça:
           u := uv.origem
           v := uv.destino     // uv é a aresta de u para v
           se v.distância > u.distância + uv.peso então:
               v.distância := u.distância + uv.peso
               v.anterior := u

   // Passo 3: Verificar a existência de ciclos com peso negativo
   para cada aresta uv em arestas faça:
       u := uv.origem
       v := uv.destino
       se v.distância < u.distância + uv.peso então:
           erro "O grafo contém um ciclo de peso negativo."

Código em C++

 
 #include <iostream> 
 #define INFINITY 0x3f3f3f3f 
 #define NODOS 1000 
 
 using namespace std; 
 
 typedef struct { 
    int source;
    int dest; //destino
    int weight; //peso
 } Edge; 
 
 int distancia[NODOS];
 
 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) { 
    int i,j,trocou;
    for (i = 0; i < nodecount; i++) {
       distancia[i] = INFINITY;
    }
    distancia[source]=0;
    for (i = 0; i < nodecount; i++) {
       trocou = 0;
       for (j = 0; j < edgecount; j++) {
          if (distancia[edges[j].dest] > distancia[edges[j].source] + edges[j].weight) {
             distancia[edges[j].dest] = distancia[edges[j].source] + edges[j].weight;
             trocou=1;
          }
       }
       // se nenhuma iteração teve efeito, futuras iterações estão dispensadas
       if (trocou==0) break;
    }
    // usado somente para detectar ciclos negativos (dispensável)
    for (i = 0; i < edgecount; i++) {
       if (distancia[edges[i].dest] > distancia[edges[i].source] + edges[i].weight) {
          cout << "Ciclo negativo de pesos de arestas detectado" << endl;
          break;
       }
    }
    for (i = 0; i < nodecount; i++) {
       cout << "A distancia mais curta entre os nodos " << source << " e " << i <<" eh " << distancia[i] << endl;
    }
 }
 
 int main (void){
    // Este caso de teste produzira as distancias entre o nodo 0 e os outros nodos
    Edge Arestas[10] = {{0, 1, 5},  {0,2, 8}, {0,3, -4}, {1,0, -2},
                         {2, 1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
                         {4,0, 6}, {4,2, 7}};
    // BellmanFord(Estrutura, arestas, vertices,origem);
    BellmanFord(Arestas, 10, 5, 0);
    return 0;
 }

Ver também

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