Algoritmo de Johnson
Algoritmo de Johnson | |
---|---|
classe | Algoritmo de busca |
estrutura de dados | Grafo |
Algoritmos | |
Esta caixa:
|
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.
Descrição do algoritmo
É formado pelos seguintes passos:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Johnson%27s_algorithm.svg/540px-Johnson%27s_algorithm.svg.png)
- Primeiro, um novo nó q é adicionado ao grafo, conectado com peso zero (0) com cada um dos outros nós.
- 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.
- 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).
- 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