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 <math>O(v \times a)</math> onde v é o número de vértices e a o número de arestas.

Pseudocódigo

// Define os tipos de dados para um grafo
registro vértice {
    lista arestas
    número distância
    vértice anterior
}
registro aresta {
    vértice origem
    vértice destino
    número peso
}

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.”

==

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

Tags: Algoritmo, perda, perda do peso