Algoritmo de Johnson

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Algoritmo de Johnson
classe Algoritmo de busca
estrutura de dados Grafo
Algoritmos

Algoritmo de Johnson é uma forma de encontrar o menor caminho entre entre dois pontos. Ele permite que algumas bordas tenham número negativo, mas ciclos negativos não devem existir. Este algoritmo trabalha com base no Algoritmo de Bellman-Ford, para computar uma transformação de um grafo de entrada, que remove todas os pesos negativos, permitindo o uso do algoritmo de Dijkstra no grafo transformado. Recebe esse nome em homenagem a Donald B. Johnson, o primeiro a descreve-lo, em 1977.

Descrição do algoritmo[editar | editar código-fonte]

É formado pelos seguintes passos:

Johnson's algorithm.svg
  1. Primeiro, um novo nó q é adicionado ao grafo, conectado com peso zero (0) com cada um dos outros nós.
  2. Segundo, é usado o algoritmo de Bellman–Ford, começando a partir do novo nó q, para encontrar cada um dos vértices v, o de menor peso h(v) do caminho de q para v. Se esse passo detectar um ciclo negativo, o algoritmo é terminado.
  3. O próxima borda do grafo original é reponderada usando os valores calculados pelo algoritmo Bellman–Ford: uma borda de u para v, tendo comprimento w(u,v), é dada pelo novo comprimento w(u,v) + h(u) −h(v).
  4. Finalmente, q é removido, e o algoritmo de Dijkstra é usado para encontrar o menor caminho para cada um dos nós s para todos os outros vértices no grafo reponderado.

Veja também[editar | editar código-fonte]

algoritmo de Bellman-Ford

Algoritmo de Dijkstra

Problema do caminho mais curto

Grafo

Ligações externas[editar | editar código-fonte]