Pesos negativos usando el algoritmo de Dijkstra

113

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

Meir
fuente
La búsqueda de caminos en general con pesos de borde negativos es extremadamente difícil. No importa qué ruta encuentre, siempre existe la posibilidad de una ruta arbitrariamente larga con un peso de borde negativo arbitrariamente grande en algún lugar a lo largo de ella. No me sorprendería si es NP completo.
Nick Johnson
4
Para cualquier otra persona que tenga esta duda, puede encontrar el camino más corto en un gráfico DADO que no tiene ciclos de peso negativos. El algoritmo anterior funcionaría si la función Relax devolviera un valor "verdadero" cuando la relajación fue realmente exitosa, en cuyo caso, el vértice adyacente "v" se pondría en cola en la cola de prioridad si no está presente, o se actualizará si ya está presente. Esto significa que los nodos visitados se pueden agregar nuevamente a la cola de prioridad a medida que se relajan.
goelakash

Respuestas:

202

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:

Figura de 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.

templatetypedef
fuente
35
Para agregar a su excelente respuesta: Dijkstra es un algoritmo codicioso es la razón de su elección miope.
blubb
4
Me gustaría señalar que, técnicamente, todos los caminos en este gráfico tienen un costo de infinito negativo cortesía del ciclo negativo A, D, B, A.
Nate
2
@ Nate- Para aclarar, todos los bordes del gráfico están dirigidos de izquierda a derecha. Fue un poco difícil representar flechas en mi arte ASCII de alta calidad. :-)
templatetypedef
2
Para aquellos que no han visto gráficos con bordes negativos antes, encuentro una interpretación útil de este gráfico como una red de carreteras de peaje, donde los pesos de los bordes dan el peaje que usted paga. La carretera -300 es una loca carretera de peaje al revés en la que te dan $ 300.
D Coetzee
3
@ SchwitJanwityanujit- Así es como funciona el algoritmo de Dijkstra. El algoritmo no explora rutas , sino que trabaja procesando nodos . Cada nodo se procesa exactamente una vez, por lo que tan pronto como procesemos el nodo B y obtengamos que su distancia es 1, nunca volveremos a visitar el nodo B ni intentaremos actualizar su distancia.
templatetypedef
25

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.

infty10000101
fuente
2. No está claro por qué crees que el tiempo sería "más parecido a Bellman-Ford" y no exponencial (que es peor que Bellman-Ford). ¿Tiene un algoritmo concreto y una prueba en mente?
Gassa
3
Para 1 .: como puede usar exactamente la misma implementación de dijkstra con el criterio de detención mencionado, que se detiene cuando la cola se vacía (ver pseudocódigo en la pregunta original), sigue siendo el algoritmo dijkstras para las rutas más cortas, aunque se comporta de manera diferente asentamiento de nodos varias veces (corrección de etiquetas).
infty10000101
1
Para 2 .: Eso fue solo una suposición, así que lo eliminaré. Creo que tienes razón con el tiempo exponencial, ya que hay exponencialmente muchos caminos que hay que explorar.
infty10000101
11

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.

amit
fuente
Además, no es necesario modificar el vértice sin bordes de peso negativos, lo que rompe por completo la suposición de que los costos de la ruta solo pueden aumentar con los bordes repetidos
prusswan
esta suposición es exactamente lo que nos permite usar S, y 'sabiendo' una vez que un vértice está en S, nunca se volverá a modificar.
amit
Tu última afirmación es incorrecta. El algoritmo publicado tiene complejidad de tiempo O (E + VlogV) cuando funciona en gráficos sin bordes negativos. No es necesario comprobar que ya hemos visitado un nodo, ya que el hecho de que haya sido visitado garantiza que el procedimiento de relajación no lo añadirá una vez más a la cola.
Pixar
7

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.

punchoyeah
fuente
4

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.

soloice
fuente
1

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.

Prusswan
fuente
esto no es posible, el gráfico está dirigido.
amit
@amit: buen punto, me lo perdí. Es hora de reconsiderar el problema
prusswan
1

"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.

Loco
fuente
0

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.

CodingLab
fuente