Pesos negativos usando el algoritmo de Dijkstra

Estoy tratando de entender por qué el algoritmo de Dijkstra no funcionará con pesos negativos. Al leer un ejemplo en Shortest Paths , estoy tratando de descubrir el siguiente escenario:

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

Desde el sitio web:

Suponiendo que todos los bordes están dirigidos de izquierda a derecha, si comenzamos con A, el algoritmo de Dijkstra elegirá el borde (A, x) minimizando d (A, A) + longitud (borde), es decir (A, B). Luego establece d (A, B) = 2 y elige otro borde (y, C) minimizando d (A, y) + d (y, C); la única opción es (A, C) y establece d (A, C) = 3. Pero nunca encuentra el camino más corto de A a B, a través de C, con una longitud total de 1.

No puedo entender por qué al usar la siguiente implementación de Dijkstra, d [B] no se actualizará a 1(Cuando el algoritmo alcance el vértice C, ejecutará una relajación en B, verá que d [B] es igual a 2, y por lo tanto actualizará su 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)
}

Gracias,

Meir

El algoritmo que ha sugerido encontrará la ruta más corta en este gráfico, pero no todos los gráficos en general. Por ejemplo, considere este gráfico:

Suponga que los bordes se dirigen de izquierda a derecha como en su ejemplo,

Su algoritmo funcionará de la siguiente manera:

1. Primero, configura d(A)a zeroy las otras distancias a infinity.
2. Luego expande el nodo A, configurando d(B)a 1, d(C)a zeroy d(D)a 99.
3. A continuación, se expande C, sin cambios netos.
4. Luego te expandes B, lo que no tiene ningún efecto.
5. Finalmente, expande D, que cambia d(B)a -201.

Tenga en cuenta que al final de esto, sin embargo, d(C)sigue siendo 0, aunque el camino más corto a Ctiene longitud -200. Por lo tanto, su algoritmo no puede calcular con precisión las distancias en algunos casos. Además, incluso si tuviera que almacenar punteros hacia atrás que indiquen cómo llegar de cada nodo al nodo de inicio A, terminaría tomando la ruta incorrecta de regreso de Ca A.

Tenga en cuenta que Dijkstra funciona incluso para pesos negativos, si el gráfico no tiene ciclos negativos, es decir, ciclos cuyo peso total es menor que cero.

Por supuesto, uno podría preguntarse por qué en el ejemplo realizado por templatetypedef Dijkstra falla a pesar de que no hay ciclos negativos, de hecho, ni siquiera ciclos. Esto se debe a que está utilizando otro criterio de parada, que mantiene el algoritmo tan pronto como se alcanza el nodo objetivo (o todos los nodos se han resuelto una vez, no lo especificó exactamente). En un gráfico sin pesos negativos, esto funciona bien.

Si uno está utilizando el criterio de parada alternativo, que detiene el algoritmo cuando la cola de prioridad (montón) se ejecuta vacía (este criterio de parada también se usó en la pregunta), entonces dijkstra encontrará la distancia correcta incluso para gráficos con pesos negativos pero sin ciclos negativos.

Sin embargo, en este caso, se pierde el límite de tiempo asintótico de dijkstra para gráficos sin ciclos negativos. Esto se debe a que un nodo asentado previamente se puede volver a insertar en el montón cuando se encuentra una mejor distancia debido a pesos negativos. Esta propiedad se denomina corrección de etiquetas.

no usó S en ninguna parte de su algoritmo (además de modificarlo). la idea de dijkstra es que una vez que un vértice está en S, no se modificará nunca más. en este caso, una vez que B esté dentro de S, no volverá a alcanzarlo por C.

este hecho asegura la complejidad de O (E + VlogV) [de lo contrario, repetirá los bordes más de una vez y los vértices más de una vez]

en otras palabras, el algoritmo que publicó, podría no estar en O (E + VlogV), como lo prometió el algoritmo de dijkstra.

Dado que Dijkstra es un enfoque codicioso, una vez que se marca un vértice como visitado para este bucle, nunca se volverá a evaluar, incluso si hay otro camino con menos costo para alcanzarlo más adelante. Y tal problema solo podría ocurrir cuando existen bordes negativos en el gráfico.

Un algoritmo codicioso , como su nombre indica, siempre toma la decisión que parece ser la mejor en ese momento. Suponga que tiene una función objetivo que debe optimizarse (maximizada o minimizada) en un punto dado. Un algoritmo codicioso toma decisiones codiciosas en cada paso para garantizar que la función objetivo esté optimizada. El algoritmo Greedy solo tiene una oportunidad para calcular la solución óptima para que nunca retroceda y revierte la decisión.

TL; DR: La respuesta depende de su implementación. Para el pseudocódigo que publicaste, funciona con pesos negativos.

Variantes del algoritmo de Dijkstra

La clave es que hay 3 tipos de implementación del algoritmo de Dijkstra , pero todas las respuestas a esta pregunta ignoran las diferencias entre estas variantes.

1. Usar un bucle anidadofor para relajar los vértices. Esta es la forma más sencilla de implementar el algoritmo de Dijkstra. La complejidad del tiempo es O (V ^ 2).
2. Implementación basada en la cola de prioridad / montón + NO se permite el reingreso , donde el reingreso significa que un vértice relajado se puede empujar nuevamente a la cola de prioridad para relajarse de nuevo más tarde .
3. Implementación basada en cola de prioridad / montón + reingreso permitido.

La versión 1 y 2 fallarán en gráficos con pesos negativos (si obtiene la respuesta correcta en tales casos, es solo una coincidencia), pero la versión 3 aún funciona .

El pseudocódigo publicado bajo el problema original es la versión 3 anterior, por lo que funciona con pesos negativos.

Aquí hay una buena referencia de Algorithm (4a edición) , que dice (y contiene la implementación de Java de la versión 2 y 3 que mencioné anteriormente):

P. ¿El algoritmo de Dijkstra funciona con pesos negativos?

R. Sí y no. Hay dos algoritmos de rutas más cortas conocidos como algoritmo de Dijkstra, dependiendo de si un vértice se puede poner en cola en la cola de prioridad más de una vez. Cuando los pesos no son negativos, las dos versiones coinciden (ya que ningún vértice se pondrá en cola más de una vez). La versión implementada en DijkstraSP.java (que permite que un vértice se ponga en cola más de una vez) es correcta en presencia de pesos de borde negativos (pero no ciclos negativos) pero su tiempo de ejecución es exponencial en el peor de los casos. (Observamos que DijkstraSP.java lanza una excepción si el dígrafo ponderado por el borde tiene un borde con un peso negativo, de modo que un programador no se sorprenda por este comportamiento exponencial). Si modificamos DijkstraSP.java para que un vértice no se pueda poner en cola más de una vez (por ejemplo, usando una matriz marcada [] para marcar los vértices que se han relajado),

Para obtener más detalles sobre la implementación y la conexión de la versión 3 con el algoritmo Bellman-Ford, consulte esta respuesta de zhihu . También es mi respuesta (pero en chino). Actualmente no tengo tiempo para traducirlo al inglés. Realmente aprecio si alguien pudiera hacer esto y editar esta respuesta en stackoverflow.

Considere lo que sucede si va y viene entre B y C ... voila

(relevante solo si el gráfico no está dirigido)

Editado: creo que el problema tiene que ver con el hecho de que la ruta con AC * solo puede ser mejor que AB con la existencia de bordes de peso negativos, por lo que no importa a dónde vaya después de AC, con el supuesto de que no bordes de peso negativos es imposible encontrar un camino mejor que AB una vez que eligió llegar a B después de ir a AC.

"2) ¿Podemos usar el algoritmo de Dijksra para las rutas más cortas para gráficos con pesos negativos? Una idea puede ser, calcular el valor de peso mínimo, agregar un valor positivo (igual al valor absoluto del valor de peso mínimo) a todos los pesos y ejecutar el algoritmo de Dijksra para el gráfico modificado. ¿Funcionará este algoritmo? "

Esto no funciona en absoluto a menos que todos los caminos más cortos tengan la misma longitud. Por ejemplo, dado un camino más corto con una longitud de dos bordes, y después de agregar un valor absoluto a cada borde, el costo total del camino se incrementa en 2 * | peso negativo máximo |. Por otro lado, otra ruta de longitud tres bordes, por lo que el costo de la ruta se incrementa en 3 * | peso negativo máximo |. Por lo tanto, todos los caminos distintos se incrementan en cantidades diferentes.

Puede usar el algoritmo de dijkstra con bordes negativos sin incluir el ciclo negativo, pero debe permitir que un vértice se pueda visitar varias veces y esa versión perderá su complejidad de tiempo rápido.

En ese caso, prácticamente he visto que es mejor usar el algoritmo SPFA que tiene una cola normal y puede manejar bordes negativos.