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 em Shortest Paths , estou tentando descobrir o seguinte cenário:

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

A partir do site:

Assumindo que as arestas sã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 nunca encontra o caminho mais curto de A para B, via C, com o comprimento total 1.

Eu 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 irá executar um relax em B, ver que o d [B] é igual a 2 , e portanto, atualize 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 ← SU {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 charts em geral. Por exemplo, considere este gráfico:

Figura do gráfico

Suponha que as bordas sejam direcionadas da esquerda para a direita, como no seu exemplo.

Seu algoritmo funcionará da seguinte maneira:

  1. Primeiro, você define d(A) como zero e o outro distancia até o infinity .
  2. Você então expande o nó A , definindo d(B) para 1 , d(C) para zero e d(D) para 99 .
  3. Em seguida, expanda C , sem alterações na rede.
  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, porém, aquele d(C) ainda é 0 , mesmo que o caminho mais curto para C tenha comprimento de -200 . Seu algoritmo não consegue calcular com precisão as distâncias em alguns casos. Além disso, mesmo que você armazenasse pointers dizendo como ir de cada nó para o nó inicial A , você terminaria tomando o caminho errado de C para A

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

É claro que alguém poderia perguntar por que, no exemplo dado por modelos, Dijkstra falha mesmo que não haja ciclos negativos, nem sequer ciclos. Isso porque ele está usando outro critério de parada, que mantém o algoritmo assim que o nó de destino é atingido (ou todos os nós foram resolvidos 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 interrompe o algoritmo quando a fila de prioridade (heap) estiver vazia (esse critério de parada também foi usado na pergunta), então dijkstra encontrará a distância correta mesmo para charts com pesos negativos, mas sem ciclos negativos.

No entanto, neste caso, o tempo assintótico ligado ao dijkstra para charts 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 label.

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

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

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

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


Um algoritmo guloso , como o nome sugere, sempre faz a escolha que parece ser a melhor naquele momento. Suponha que você tenha uma function objetiva que precisa ser otimizada (maximizada ou minimizada) em um determinado ponto. Um algoritmo Greedy faz escolhas gananciosas em cada etapa para garantir que a function objective seja otimizada. O algoritmo Greedy tem apenas uma chance para calcular a solução ótima, para que ela nunca retorne e reverta a decisão.

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 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ê escolheu alcançar B depois de ir AC.

“2) Podemos usar o algoritmo de Dijksra para caminhos mais curtos para charts com pesos negativos – uma idéia pode ser, calcular o valor mínimo de peso, adicionar um valor positivo (igual ao valor absoluto do peso mínimo) a 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 tamanho. Por exemplo, dado um caminho mais curto de duas arestas de comprimento e depois de adicionar valor absoluto a cada aresta, o custo total do caminho é aumentado em 2 * | peso negativo máx |. Por outro lado, outro caminho de comprimento de três arestas, de modo que o custo do caminho é aumentado em 3 * | peso negativo máximo |. Assim, todos os caminhos distintos são aumentados em quantidades diferentes.