Por que o algoritmo de Dijkstra não funciona para arestas de peso negativo?

Alguém pode me dizer por que o algoritmo de Dijkstra para o caminho mais curto de fonte única assume que as arestas devem ser não negativas.

Estou falando apenas de bordas, não dos ciclos de peso negativo.

Lembre-se que no algoritmo de Dijkstra, uma vez que um vértice é marcado como "fechado" (e fora do conjunto aberto) - o algoritmo encontrou o caminho mais curto para ele e nunca terá que desenvolver este nó novamente - ele assume o caminho desenvolvido para este o caminho é o mais curto.

Mas com pesos negativos - pode não ser verdade. Por exemplo:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Dijkstra de A primeiro desenvolverá C e, mais tarde, não conseguirá encontrar A->B->C

EDITAR uma explicação um pouco mais profunda:

Observe que isso é importante, porque em cada etapa de relaxamento, o algoritmo assume que o "custo" para os nós "fechados" é de fato mínimo e, portanto, o nó que será selecionado a seguir também é mínimo.

A ideia é: se tivermos um vértice aberto de modo que seu custo seja mínimo - adicionando qualquer número positivo a qualquer vértice - a minimalidade nunca mudará.
Sem a restrição de números positivos - a suposição acima não é verdadeira.

Uma vez que "sabemos" cada vértice que foi "fechado" é mínimo - podemos fazer a etapa de relaxamento com segurança - sem "olhar para trás". Se precisarmos "olhar para trás", a Bellman-Ford oferece uma solução recursiva (DP) para fazer isso.

Considere o gráfico mostrado abaixo com a fonte como Vértice A. Primeiro tente executar o algoritmo de Dijkstra nele.

Quando me refiro ao algoritmo de Dijkstra em minha explicação, estarei falando sobre o algoritmo de Dijkstra conforme implementado abaixo,

Portanto, começando com os valores ( a distância da fonte ao vértice ) inicialmente atribuídos a cada vértice são,

Primeiro extraímos o vértice em Q = [A, B, C] que possui o menor valor, ou seja, A, após o qual Q = [B, C] . Nota A tem uma aresta direcionada para B e C, também ambos estão em Q, portanto, atualizamos ambos os valores,

Agora extraímos C como (2 <5), agora Q = [B] . Observe que C não está conectado a nada, então o line16loop não funciona.

Finalmente extraímos B, após o qual . Nota B tem um bordo dirigido para C mas não C está presente em Q, por conseguinte, mais uma vez não entram no loop for em line16,

Então acabamos com as distâncias como

Observe como isso está errado, pois a distância mais curta de A a C é 5 + -10 = -5, quando você vai .

Portanto, para este gráfico, o Algoritmo de Dijkstra calcula erroneamente a distância de A a C.

Isso acontece porque o algoritmo de Dijkstra não tentar encontrar um caminho mais curto para vértices que são já extraídos Q .

O que o line16loop está fazendo é pegar o vértice u e dizer "ei, parece que podemos ir para v da fonte via u , essa distância (alt ou alternativa) é melhor do que a dist [v] atual que obtivemos? Se sim, vamos atualizar dist [v] "

Note-se que no line16que verificar todos vizinhos v (isto é, um bordo dirigido existe a partir de u para v ), de L que estão ainda em Q . Em line14eles removem notas visitada de Q. Então, se x é um vizinho visitada de u , o caminho é nem mesmo considerado como um possível caminho mais curto da origem para o v .

Em nosso exemplo acima, C era um vizinho visitado de B, portanto, o caminho não foi considerado, deixando o caminho mais curto atual inalterado.

Isso é realmente útil se os pesos das arestas forem todos números positivos , porque então não perderíamos nosso tempo considerando caminhos que não podem ser mais curtos.

Portanto, digo que ao executar esse algoritmo se x for extraído de Q antes de y , não será possível encontrar um caminho - que é mais curto. Deixe-me explicar isso com um exemplo,

Como y acabou de ser extraído e x foi extraído antes de si mesmo, então dist [y]> dist [x], caso contrário, y teria sido extraído antes de x . ( line 13distância mínima primeiro)

E como já assumimos que os pesos das arestas são positivos, ou seja, comprimento (x, y)> 0 . Portanto, a distância alternativa (alt) por meio de y é sempre maior, ou seja, dist [y] + comprimento (x, y)> dist [x] . Portanto, o valor de dist [x] não teria sido atualizado mesmo se y fosse considerado um caminho para x , portanto, concluímos que faz sentido considerar apenas os vizinhos de y que ainda estão em Q (observe o comentário em line16)

Mas isso depende de nossa suposição de comprimento positivo da aresta, se comprimento (u, v) <0, então, dependendo de quão negativa é essa aresta, podemos substituir dist [x] após a comparação em line18.

Portanto, qualquer cálculo dist [x] que fizermos será incorreto se x for removido antes de todos os vértices v - de modo que x é um vizinho de v com aresta negativa conectando-os - sejam removidos.

Porque cada um desses v vértices é o segundo último vértice em um caminho "melhor" potencial da origem até x , que é descartado pelo algoritmo de Dijkstra.

Portanto, no exemplo que dei acima, o erro foi porque C foi removido antes de B ser removido. Enquanto aquele C era vizinho de B com uma borda negativa!

Só para esclarecer, B e C são vizinhos de A. B tem um único vizinho C e C não tem vizinhos. comprimento (a, b) é o comprimento da aresta entre os vértices a e b.

O algoritmo de Dijkstra assume que os caminhos só podem se tornar "mais pesados", de modo que se você tiver um caminho de A para B com peso 3 e um caminho de A a C com peso 3, não há como adicionar uma aresta e vá de A para B por meio de C com peso menor que 3.

Essa suposição torna o algoritmo mais rápido do que os algoritmos que precisam levar em consideração pesos negativos.

Exatidão do algoritmo de Dijkstra:

Temos 2 conjuntos de vértices em qualquer etapa do algoritmo. O conjunto A consiste nos vértices para os quais calculamos os caminhos mais curtos. O conjunto B consiste nos vértices restantes.

Hipótese indutiva : em cada etapa, assumiremos que todas as iterações anteriores estão corretas.

Etapa indutiva : Quando adicionamos um vértice V ao conjunto A e definimos a distância como dist [V], devemos provar que essa distância é ótima. Se isso não for o ideal, deve haver algum outro caminho para o vértice V que seja de menor comprimento.

Suponha que algum outro caminho passe por algum vértice X.

Agora, como dist [V] <= dist [X], portanto, qualquer outro caminho para V terá pelo menos dist [V] comprimento, a menos que o gráfico tenha comprimentos de borda negativos.

Portanto, para que o algoritmo de dijkstra funcione, os pesos das arestas devem ser não negativos.

Experimente o algoritmo de Dijkstra no gráfico a seguir, supondo que Aseja o nó de origem, para ver o que está acontecendo:

Lembre-se de que no algoritmo de Dijkstra, uma vez que um vértice é marcado como "fechado" (e fora do conjunto aberto) - ele assume que qualquer nó originado dele levará a uma distância maior , então, o algoritmo encontrou o caminho mais curto para ele, e nunca terá que desenvolver este nó novamente, mas isso não é verdade no caso de pesos negativos.

As outras respostas até agora demonstram muito bem por que o algoritmo de Dijkstra não consegue lidar com pesos negativos em caminhos.

Mas a própria questão talvez esteja baseada em uma compreensão errada do peso dos caminhos. Se pesos negativos em caminhos fossem permitidos em algoritmos de pathfinding em geral, você obteria loops permanentes que não parariam.

Considere isto:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

Qual é o caminho ideal entre A e D?

Qualquer algoritmo de localização de caminho teria que fazer um loop contínuo entre B e C, pois isso reduziria o peso do caminho total. Portanto, permitir pesos negativos para uma conexão tornaria qualquer algoritmo pathfindig discutível, talvez exceto se você limitar cada conexão para ser usada apenas uma vez.

Você pode usar o algoritmo de dijkstra com arestas negativas não incluindo ciclo negativo, mas você 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.