Algoritmo de Bellman-Ford

Origem: Wikipédia, a enciclopédia livre.

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.

Este artigo é um esboço sobre Programação. Você pode ajudar a Wikipédia expandindo-o.

[editar] 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
   para cada vértice v em vértices faça:
       para cada aresta uv em v.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."