Pesos negativos usando o algoritmo de Dijkstra

Estou tentando entender por que o algoritmo de Dijkstra não funciona com pesos negativos. Lendo um exemplo sobre Shortest Paths , estou tentando descobrir o seguinte cenário:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

A partir do site:

Assumindo que as arestas estão todas direcionadas da esquerda para a direita, se começarmos com A, o algoritmo de Dijkstra escolherá a aresta (A, x) minimizando d (A, A) + comprimento (aresta), a saber (A, B). Em seguida, define d (A, B) = 2 e escolhe outra aresta (y, C) minimizando d (A, y) + d (y, C); a única escolha é (A, C) e define d (A, C) = 3. Mas ele nunca encontra o caminho mais curto de A para B, via C, com comprimento total 1.

Não consigo entender por que usar a seguinte implementação de Dijkstra, d [B] não será atualizado para 1(Quando o algoritmo atinge o vértice C, ele executa um relaxamento em B, veja que ad [B] é igual a 2e, portanto, atualiza seu valor para 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

Obrigado,

Meir

O algoritmo que você sugeriu realmente encontrará o caminho mais curto neste gráfico, mas nem todos os gráficos em geral. Por exemplo, considere este gráfico:

Suponha que as bordas são direcionadas da esquerda para a direita como no seu exemplo,

Seu algoritmo funcionará da seguinte maneira:

1. Primeiro, você define d(A)como zeroe as outras distâncias como infinity.
2. Em seguida, você expande o nó A, definindo d(B)para 1, d(C)para zeroe d(D)para 99.
3. Em seguida, você expande C, sem alterações líquidas.
4. Você então expande B, o que não tem efeito.
5. Finalmente, você expande D, que muda d(B)para -201.

Observe que, no final disso, ainda d(C)é 0, embora o caminho mais curto para Ctenha comprimento -200. Seu algoritmo, portanto, falha em calcular distâncias com precisão em alguns casos. Além disso, mesmo se você fosse armazenar ponteiros de volta dizendo como ir de cada nó ao nó inicial A, acabaria tomando o caminho errado de volta Cpara A.

Observe que Dijkstra funciona mesmo para pesos negativos, se o gráfico não tiver ciclos negativos, ou seja, ciclos cujo peso somado é menor que zero.

Claro que se pode perguntar, por que no exemplo feito por templatetypedef Dijkstra falha mesmo que não haja ciclos negativos, na verdade nem mesmo ciclos. Isso porque ele está usando outro critério de parada, que mantém o algoritmo assim que o nó de destino é alcançado (ou todos os nós foram fixados uma vez, ele não especificou exatamente). Em um gráfico sem pesos negativos, isso funciona bem.

Se alguém estiver usando o critério de parada alternativo, que para o algoritmo quando a fila de prioridade (heap) executa vazia (este critério de parada também foi usado na pergunta), então dijkstra encontrará a distância correta mesmo para gráficos com pesos negativos, mas sem ciclos negativos.

No entanto, neste caso, o limite de tempo assintótico de dijkstra para gráficos sem ciclos negativos é perdido. Isso ocorre porque um nó previamente estabelecido pode ser reinserido no heap quando uma distância melhor é encontrada devido a pesos negativos. Essa propriedade é chamada de correção de rótulo.

você não usou S em nenhum lugar em seu algoritmo (além de modificá-lo). a ideia de dijkstra é que uma vez que um vértice está em S, ele não será modificado nunca mais. neste caso, uma vez que B está dentro de S, você não o alcançará novamente por C.

este fato garante a complexidade de O (E + VlogV) [caso contrário, você repetirá as arestas mais de uma vez e os vértices mais de uma vez]

em outras palavras, o algoritmo que você postou pode não estar em O (E + VlogV), conforme prometido pelo algoritmo de dijkstra.

Como Dijkstra é uma abordagem Greedy, uma vez que um vértice é marcado como visitado para este loop, ele nunca seria reavaliado novamente, mesmo se houver outro caminho com menor custo para alcançá-lo posteriormente. E tal problema só poderia acontecer quando existirem arestas negativas no gráfico.

UMA algoritmo ganancioso , como o nome sugere, sempre faz a escolha que parece ser a melhor naquele momento. Suponha que você tenha uma função objetivo que precisa ser otimizada (maximizada ou minimizada) em um determinado ponto. Um algoritmo Greedy faz escolhas gananciosas em cada etapa para garantir que a função objetivo seja otimizada. O algoritmo Greedy tem apenas uma tentativa para calcular a solução ótima, de modo que nunca volte e reverta a decisão.

TL; DR: A resposta depende da sua implementação. Para o pseudo código que você postou, ele funciona com pesos negativos.

Variantes do Algoritmo de Dijkstra

A chave é que existem 3 tipos de implementação do algoritmo de Dijkstra , mas todas as respostas sob esta questão ignoram as diferenças entre essas variantes.

1. Usando um -loop aninhadofor para relaxar os vértices. Esta é a maneira mais fácil de implementar o algoritmo de Dijkstra. A complexidade do tempo é O (V ^ 2).
2. Implementação baseada em fila de prioridade / heap + NENHUMA reentrada permitida, onde a reentrada significa que um vértice relaxado pode ser empurrado para a fila de prioridade novamente para ser relaxado novamente mais tarde .
3. Implementação baseada em fila de prioridade / heap + reentrada permitida.

As versões 1 e 2 falharão em gráficos com pesos negativos (se você obtiver a resposta correta em tais casos, é apenas uma coincidência), mas a versão 3 ainda funciona .

O pseudocódigo postado sob o problema original é a versão 3 acima, portanto, funciona com pesos negativos.

Aqui está uma boa referência do Algorithm (4ª edição) , que diz (e contém a implementação java das versões 2 e 3 que mencionei acima):

P. O algoritmo de Dijkstra funciona com pesos negativos?

A. Sim e não. Existem dois algoritmos de caminhos mais curtos conhecidos como algoritmo de Dijkstra, dependendo se um vértice pode ser enfileirado na fila de prioridade mais de uma vez. Quando os pesos são não negativos, as duas versões coincidem (já que nenhum vértice será enfileirado mais de uma vez). A versão implementada em DijkstraSP.java (que permite que um vértice seja enfileirado mais de uma vez) está correta na presença de pesos de aresta negativos (mas sem ciclos negativos), mas seu tempo de execução é exponencial no pior caso. (Notamos que DijkstraSP.java lança uma exceção se o dígrafo de aresta ponderada tiver uma aresta com peso negativo, de modo que um programador não se surpreenda com esse comportamento exponencial.) Se modificarmos DijkstraSP.java de modo que um vértice não possa ser enfileirado mais de uma vez (por exemplo, usando uma matriz marcada [] para marcar os vértices que foram relaxados),

Para obter mais detalhes de implementação e a conexão da versão 3 com o algoritmo Bellman-Ford, consulte esta resposta de zhihu . É também a minha resposta (mas em chinês). Atualmente não tenho tempo de traduzir para o inglês. Eu realmente aprecio se alguém pudesse fazer isso e editar esta resposta no stackoverflow.

Considere o que acontece se você vai e volta entre B e C ... voila

(relevante apenas se o gráfico não for direcionado)

Editado: Eu acredito que o problema tem a ver com o fato de que o caminho com AC * só pode ser melhor do que AB com a existência de bordas de peso negativo, então não importa para onde você vai depois de AC, com a suposição de não bordas de peso negativo, é impossível encontrar um caminho melhor do que AB, uma vez que você optou por alcançar B após ir para AC.

"2) Podemos usar o algoritmo de Dijksra para caminhos mais curtos para gráficos com pesos negativos - uma ideia pode ser, calcular o valor de peso mínimo, adicionar um valor positivo (igual ao valor absoluto do valor de peso mínimo) para todos os pesos e executar o algoritmo de Dijksra para o gráfico modificado. Esse algoritmo funcionará? "

Isso absolutamente não funciona, a menos que todos os caminhos mais curtos tenham o mesmo comprimento. Por exemplo, dado um caminho mais curto com comprimento de duas arestas, e depois de adicionar valor absoluto a cada aresta, o custo total do caminho é aumentado em 2 * | peso negativo máximo |. Por outro lado, outro caminho de comprimento de três arestas, portanto, o custo do caminho é aumentado em 3 * | peso negativo máximo |. Conseqüentemente, todos os caminhos distintos são aumentados em valores diferentes.

Você pode usar o algoritmo de dijkstra com arestas negativas sem incluir ciclo negativo, mas deve permitir que um vértice possa ser visitado várias vezes e essa versão perderá sua complexidade de tempo rápido.

Nesse caso, praticamente vi que é melhor usar o algoritmo SPFA que tem fila normal e pode lidar com bordas negativas.