Algoritmo da Matriz de Custo Geral

 

AUTORES: Ford, Moore, Bellman

 

DATA: em torno de 1950

 

NOMENCLATURA:

                :  label do vértice xi depois de k+1 iterações.

       S       :  conjunto de todos os vértices cujos caminhos mais curtos atuais desde s são de Cardinalidade k.

       Ti      :  conjunto de vértices para os quais os caminhos mais curtos atuais dede s são de Cardinalidade k e no qual um arco xi existe.

 

FUNDAMENTOS:

É um método iterativo baseado na designação de labels nos vértices. No final da iteração k, os labels representam os valores dos caminhos mais curtos destes que contêm k+1 ou menos arcos.

 

OBSERVAÇÃO: Diferente de Dijstra, nenhum label pode ser considerado permanente no processo até que todos os sejam.

 

ALGORITMO CONCEITUAL

Passo 1: INICIALIZAÇÃO

   - calcular                para todo xi ≠ s

   - S=Γ(s), k=1, l’(s)=0,

   - l’(xi)=C(s,xi) para xi ∈ S

   - l’(xi)=0 para xi ∉ S

 

Passo 2: ATUALIZAÇÃO DOS LABELS

   a. Determinar vértices cujos labels podem ser modificados → xi ∈ Γ(s), xi ≠ s

   b. Determinar Ti=           ∩ S para xi ∈ Γ(s), xi ≠ s

   c. Atualizar os labels

 

 

 

Passo 3: TESTE DE FINALIZAÇÃO

  

 

 

 

Passo 4: ATUALIZAÇÃO DE S

 

 

Passo 5: INCREMENTO DE K

   k=k+1 Volte ao Passo 2.

 

 

OBSERVAÇÃO: Este algoritmo pode ser usado para Cij=0, desde que não exista no grafo um Circuito cujo Custo seja Negativo.