Algoritmo de Johnson

Algoritmo de Johnson é uma forma de encontrar o menor caminho entre entre dois pontos. Ele permite que algumas arestas 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 descrevê-lo, em 1977.

Algoritmo de Johnson
classe	Algoritmo de busca
estrutura de dados	Grafo
Algoritmos

Descrição do algoritmo

É formado pelos seguintes passos:

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.

Exemplo de código em c++:

#include<iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b){
   return (a<b)?a:b;
}
main() {
   int vert, edge, i, j, k, c;
   cout << "Enter no of vertices: ";
   cin >> vert;
   cout << "Enter no of edges: ";
   cin >> edge;
   cout << "Enter the EDGE Costs:\n";
   for (k = 1; k <= edge; k++) { //take the input and store it into adj and cost matrix
      cin >> i >> j >> c;
      adj[i][j] = cost[i][j] = c;
   }
   for (i = 1; i <= vert; i++)
      for (j = 1; j <= vert; j++) {
         if (adj[i][j] == 0 && i != j)
            adj[i][j] = INF; //if there is no edge, put infinity
      }
   for (k = 1; k <= vert; k++)
      for (i = 1; i <= vert; i++)
         for (j = 1; j <= vert; j++)
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); //find minimum path from i to j through k
   cout << "Resultant adj matrix\n";
   for (i = 1; i <= vert; i++) {
      for (j = 1; j <= vert; j++) {
            if (adj[i][j] != INF)
               cout << adj[i][j] << " ";
      }
      cout << "\n";
   }
}

Saída:

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0

Veja também

algoritmo de Bellman-Ford

Algoritmo de Dijkstra

Problema do caminho mais curto

Grafo

Ligações externas

• Boost: All Pairs Shortest Paths