Algoritmo de Johnson - Johnson's algorithm

Algoritmo de johnson
Classe	Problema de caminho mais curto de todos os pares (para gráficos ponderados)
Estrutura de dados	Gráfico
Desempenho de pior caso

O algoritmo de Johnson é uma maneira de encontrar os caminhos mais curtos entre todos os pares de vértices em um grafo direcionado com aresta ponderada . Ele permite que alguns dos pesos das arestas sejam números negativos , mas nenhum ciclo de peso negativo pode existir. Ele funciona usando o algoritmo Bellman-Ford para calcular uma transformação do gráfico de entrada que remove todos os pesos negativos, permitindo que o algoritmo de Dijkstra seja usado no gráfico transformado. Recebeu o nome de Donald B. Johnson , que publicou a técnica pela primeira vez em 1977.

Uma técnica de reponderação semelhante também é usada no algoritmo de Suurballe para encontrar dois caminhos disjuntos de comprimento total mínimo entre os mesmos dois vértices em um gráfico com pesos de aresta não negativos.

Descrição do algoritmo

O algoritmo de Johnson consiste nas seguintes etapas:

Primeiro, um novo nó $q$ é adicionado ao grafo, conectado por arestas de peso zero a cada um dos outros nós.
Em segundo lugar, o algoritmo Bellman-Ford é usado, partindo do novo vértice $q$ , para encontrar para cada vértice $v$ o peso mínimo $h (v)$ de um caminho de $q$ a $v$ . Se esta etapa detectar um ciclo negativo, o algoritmo é encerrado.
Em seguida, as arestas do gráfico original são reponderadas usando os valores calculados pelo algoritmo Bellman-Ford: uma aresta de $u$ a $v$ , tendo comprimento , recebe o novo comprimento $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . ${\ displaystyle w (u, v)}$
Finalmente, $q$ é removido e o algoritmo de Dijkstra é usado para encontrar os caminhos mais curtos de cada nó $s$ para todos os outros vértices no grafo reponderado. A distância no gráfico original é então calculada para cada distância $D$ ( $u$ , $v$ ), adicionando $h (v) - h (u)$ à distância retornada pelo algoritmo de Dijkstra.

Exemplo

Os primeiros três estágios do algoritmo de Johnson são descritos na ilustração abaixo.

O gráfico à esquerda da ilustração possui duas arestas negativas, mas nenhum ciclo negativo. O gráfico central mostra o novo vértice $q$ , uma árvore de caminho mais curto calculado pelo algoritmo Bellman-Ford com $q$ como vértice inicial, e os valores $h (v)$ calculados em cada outro nó como o comprimento do caminho mais curto de $q$ para aquele nó. Observe que esses valores são todos não positivos, porque $q$ tem uma aresta de comprimento zero para cada vértice e o caminho mais curto não pode ser maior do que essa aresta. À direita é mostrado o gráfico reponderado, formado pela substituição de cada peso da aresta por $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . Neste gráfico reponderado, todos os pesos de aresta são não negativos, mas o caminho mais curto entre quaisquer dois nós usa a mesma sequência de arestas que o caminho mais curto entre os mesmos dois nós no gráfico original. O algoritmo conclui aplicando o algoritmo de Dijkstra a cada um dos quatro nós iniciais no grafo reponderado. ${\ displaystyle w (u, v)}$

Exatidão

No grafo reponderado, todos os caminhos entre um par $s$ e $t$ de nós têm a mesma quantidade $h (s) - h (t)$ adicionada a eles. A afirmação anterior pode ser comprovada da seguinte maneira: Seja $p$ um caminho. Seu peso W no gráfico reponderado é dado pela seguinte expressão: ${\ displaystyle st}$

{\ displaystyle {\ bigl (} w (s, p_ {1}) + h (s) -h (p_ {1}) {\ bigr)} + ​​{\ bigl (} w (p_ {1}, p_ { 2}) + h (p_ {1}) - h (p_ {2}) {\ bigr)} + ​​... + {\ bigl (} w (p_ {n}, t) + h (p_ {n} ) -h (t) {\ bigr)}.}

Cada é cancelado por na expressão entre colchetes anterior; portanto, ficamos com a seguinte expressão para W : ${\ displaystyle + h (p_ {i})}$ ${\ displaystyle -h (p_ {i})}$

{\ displaystyle {\ bigl (} w (s, p_ {1}) + w (p_ {1}, p_ {2}) + ... + w (p_ {n}, t) {\ bigr)} + h (s) -h (t)}

A expressão entre colchetes é o peso de p na ponderação original.

Uma vez que a reponderação adiciona a mesma quantidade ao peso de cada caminho, um caminho é o caminho mais curto na ponderação original se e somente se for um caminho mais curto após a reponderação. O peso das arestas que pertencem a um caminho mais curto de q para qualquer nó é zero e, portanto, os comprimentos dos caminhos mais curtos de q para cada nó tornam-se zero no grafo reponderado; no entanto, eles ainda permanecem caminhos mais curtos. Portanto, não pode haver arestas negativas: se a aresta uv teve um peso negativo após a reponderação, então o caminho de comprimento zero de q a u junto com esta aresta formaria um caminho de comprimento negativo de q a v , contradizendo o fato de que todos os vértices têm distância zero de q . A inexistência de arestas negativas garante a otimização dos caminhos encontrados pelo algoritmo de Dijkstra. As distâncias no gráfico original podem ser calculadas a partir das distâncias calculadas pelo algoritmo de Dijkstra no gráfico reponderado, revertendo a transformação de reponderação. ${\ displaystyle st}$

Análise

A complexidade de tempo desse algoritmo, usando pilhas de Fibonacci na implementação do algoritmo de Dijkstra, é : o algoritmo usa o tempo para o estágio Bellman-Ford do algoritmo e para cada uma das instanciações do algoritmo de Dijkstra. Assim, quando o gráfico é esparso , o tempo total pode ser mais rápido do que o algoritmo Floyd – Warshall , que resolve o mesmo problema no tempo . ${\ displaystyle O (| V | ^ {2} \ log | V | + | V || E |)}$ ${\ displaystyle O (| V || E |)}$ ${\ displaystyle O (| V | \ log | V | + | E |)}$ ${\ displaystyle | V |}$ ${\ displaystyle O (| V | ^ {3})}$