¿Por qué no funciona el algoritmo de Dijkstra para bordes de peso negativos?

Respuestas:

175

Recuerde que en el algoritmo de Dijkstra, una vez que un vértice se marca como "cerrado" (y fuera del conjunto abierto), el algoritmo encontró el camino más corto hacia él y nunca más tendrá que desarrollar este nodo, asume el camino desarrollado hasta este El camino es el más corto.

Pero con pesos negativos, puede que no sea cierto. Por ejemplo:

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

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

Dijkstra de A primero desarrollará C, y luego no podrá encontrar A->B->C


EDITAR una explicación un poco más profunda:

Tenga en cuenta que esto es importante, porque en cada paso de relajación, el algoritmo asume que el "costo" para los nodos "cerrados" es realmente mínimo y, por lo tanto, el nodo que se seleccionará a continuación también es mínimo.

La idea es: si tenemos un vértice abierto de modo que su costo sea mínimo, agregando cualquier número positivo a cualquier vértice, la minimidad nunca cambiará.
Sin la restricción de números positivos, el supuesto anterior no es cierto.

Ya que "sabemos" que cada vértice que estaba "cerrado" es mínimo - podemos hacer el paso de relajación con seguridad - sin "mirar atrás". Si necesitamos "mirar hacia atrás", Bellman-Ford ofrece una solución de tipo recursivo (DP) para hacerlo.

amit
fuente
5
Lo siento, pero no recibo ningún error. Primero A->Bserá 5 y A->Cserá 2. Luego B->Cserá -5. Entonces el valor de Cserá el -5mismo que Bellman-Ford. ¿Cómo es que esto no da la respuesta correcta?
Anirban Nag 'tintinmj'
5
@tintinmj primero, Dijkstra "cerrará" el nodo Acon valor de 0. Luego, buscará en el nodo de valor mínimo, Bes 5 y Ces 2. El mínimo es C, por lo que se cerrará Ccon el valor 2 y nunca mirará hacia atrás, cuando más tarde Bestá cerrado, no puede modificar el valor de C, ya que ya está "cerrado".
amit
4
@amit ¿Cómo el algoritmo de Dijkstra no encuentra el camino A -> B -> C? Primero actualizará Cla distancia a 2, y luego Bla distancia a 5. Suponiendo que en su gráfico no hay bordes salientes C, entonces no hacemos nada durante la visita C(y su distancia sigue siendo 2). Luego visitamos Dlos nodos adyacentes, y el único nodo adyacente es C, cuya nueva distancia es -5. Tenga en cuenta que en el algoritmo de Dijkstra, también hacemos un seguimiento del padre desde el que llegamos (y actualizamos) al nodo, y al hacerlo C, obtendrá el padre By A, a continuación , obtendrá un resultado correcto. ¿Qué me estoy perdiendo?
2015
12
@amit El problema con tu razonamiento (creo), y he visto a otras personas hacerlo (extrañamente), es que crees que el algoritmo no reconsiderará los nodos cuya distancia más corta ya ha sido determinada (y con la que hemos terminado), pero esto no es correcto, y es por eso que tenemos el paso de "relajación" ... iteramos a través de todos los nodos del gráfico y, para cada uno de ellos, iteramos a través de los nodos adyacentes, incluso si alguno de los nodos adyacentes podría ya se han eliminado de nuestra cola de prioridad mínima, por ejemplo.
nbro
10
@amit Verifique esta respuesta a una pregunta similar, donde el ejemplo realmente tiene sentido: stackoverflow.com/a/6799344/3924118
nbro
37

Considere el gráfico que se muestra a continuación con la fuente como Vértice A. Primero intente ejecutar el algoritmo de Dijkstra usted mismo en él.

ingrese la descripción de la imagen aquí

Cuando me refiera al algoritmo de Dijkstra en mi explicación, hablaré sobre el algoritmo de Dijkstra como se implementa a continuación,

Algoritmo de Dijkstra

Entonces, comenzando los valores ( la distancia desde la fuente al vértice ) inicialmente asignados a cada vértice son,

inicialización

Primero extraemos el vértice en Q = [A, B, C] que tiene el valor más pequeño, es decir, A, después de lo cual Q = [B, C] . Tenga en cuenta que A tiene un borde dirigido a B y C, también ambos están en Q, por lo tanto, actualizamos ambos valores,

primera iteración

Ahora extraemos C como (2 <5), ahora Q = [B] . Tenga en cuenta que C no está conectado a nada, por lo que el line16bucle no se ejecuta.

segunda iteración

Finalmente extraemos B, tras lo cual Q es Phi. Nota B tiene un borde dirigido a C pero C no está presente en Q, por lo tanto, nuevamente no ingresamos el bucle for line16,

Tercero?

Así que terminamos con las distancias como

no hay cambio chicos

Tenga en cuenta que esto está mal, ya que la distancia más corta de A a C es 5 + -10 = -5, cuando vaya a a b a c.

Entonces, para este gráfico, el algoritmo de Dijkstra calcula incorrectamente la distancia de A a C.

Esto sucede porque el algoritmo de Dijkstra no trata de encontrar un camino más corto a los vértices que están ya extraen de Q .

Lo que hace el line16bucle es tomar el vértice u y decir "parece que podemos ir av desde la fuente a través de u , ¿esa distancia (alternativa o alternativa) es mejor que la dist [v] actual que tenemos? Si es así, actualice dist [v] "

Nótese que en line16comprueban todos los vecinos v (es decir, existe una arista dirigida de u para v ), de U que están todavía en Q . En line14sacan notas visitados de P. Así que si x es un vecino visitado de U , el camino fuente a u a xestá ni siquiera considerado como un posible camino más corto desde la fuente hasta v .

En nuestro ejemplo anterior, C era un vecino visitado de B, por lo que la ruta A a B a Cno se consideró, dejando la ruta más corta actual A a Csin cambios.

Esto es realmente útil si los pesos de los bordes son todos números positivos , porque entonces no perderíamos nuestro tiempo considerando caminos que no pueden ser más cortos.

Entonces digo que al ejecutar este algoritmo, si x se extrae de Q antes de y , entonces no es posible encontrar una ruta, imposibleque es más corta. Déjame explicarte esto con un ejemplo,

Como y se acaba de extraer y x se extrajo antes que él mismo, entonces dist [y]> dist [x] porque de lo contrario y se habría extraído antes que x . ( line 13distancia mínima primero)

Y como ya supusimos que los pesos de borde son, positivo, es decir la longitud (x, y)> 0 . Por tanto, la distancia alternativa (alt) a través de y siempre será mayor, es decir, dist [y] + length (x, y)> dist [x] . Entonces, el valor de dist [x] no se habría actualizado incluso si y se considerara una ruta ax , por lo que concluimos que tiene sentido considerar solo los vecinos de y que todavía están en Q (observe el comentario en line16)

Pero esto depende de nuestra suposición de longitud de borde positiva, si la longitud (u, v) <0, entonces, dependiendo de qué tan negativo sea ese borde, podríamos reemplazar la dist [x] después de la comparación en line18.

Entonces, cualquier cálculo de dist [x] que hagamos será incorrecto si x se elimina antes de que se eliminen todos los vértices v , de manera que x es un vecino de v con un borde negativo que los conecta.

Porque cada uno de esos v vértices es el penúltimo vértice en un camino "mejor" potencial desde la fuente hasta x , que es descartado por el algoritmo de Dijkstra.

Entonces, en el ejemplo que di arriba, el error fue porque se eliminó C antes de eliminar B. ¡Mientras que C era un vecino de B con una ventaja negativa!

Solo para aclarar, B y C son vecinos de A. B tiene un solo vecino C y C no tiene vecinos. length (a, b) es la longitud del borde entre los vértices ay b.

Aditya P
fuente
2
Como dijiste, la mejor manera de resolver esto es usar el método heapq.heappush después de cada comparación. Rechazamos la distancia actualizada en la cola. Bajo esta condición, los Dijkstra pueden trabajar con pesos negativos. Lo intenté y el resultado fue 0,5, -5
nosense
1
"la fuente de la ruta axa u ni siquiera se considera"; ¿te refieres a la fuente a la x?
slmatrix
1
@slmatrix gracias por captar eso, sí, quise decir que el camino desde la fuente hasta u hasta x, porque x es un vecino de u.
Aditya P
23

El algoritmo de Dijkstra asume que las rutas solo pueden volverse 'más pesadas', por lo que si tiene una ruta de A a B con un peso de 3 y una ruta de A a C con un peso de 3, no hay forma de que pueda agregar un borde y ir de A a B pasando por C con un peso inferior a 3.

Esta suposición hace que el algoritmo sea más rápido que los algoritmos que deben tener en cuenta los pesos negativos.

zmbq
fuente
8

Corrección del algoritmo de Dijkstra:

Tenemos 2 conjuntos de vértices en cualquier paso del algoritmo. El conjunto A consta de los vértices para los que hemos calculado las rutas más cortas. El conjunto B consta de los vértices restantes.

Hipótesis inductiva : En cada paso asumiremos que todas las iteraciones anteriores son correctas.

Paso inductivo : cuando agregamos un vértice V al conjunto A y establecemos la distancia en dist [V], debemos demostrar que esta distancia es óptima. Si esto no es óptimo, entonces debe haber algún otro camino hacia el vértice V que sea de menor longitud.

Supongamos que este otro camino pasa por algún vértice X.

Ahora, dado que dist [V] <= dist [X], por lo tanto, cualquier otra ruta a V tendrá al menos una longitud de dist [V], a menos que el gráfico tenga longitudes de borde negativas.

Por lo tanto, para que funcione el algoritmo de dijkstra, los pesos de los bordes deben ser no negativos.

Nikunj Banka
fuente
6

Pruebe el algoritmo de Dijkstra en el siguiente gráfico, asumiendo que Aes el nodo fuente, para ver qué está sucediendo:

Grafico

tuberculosis-
fuente
6
Lo siento, pero no recibo ningún error. Primero A->Bvoluntad 1y A->Cvoluntad 100. Entonces lo B->Dharé 2. Entonces lo C->Dharé -4900. Entonces el valor de Dserá el -4900mismo que Bellman-Ford. ¿Cómo es que esto no da la respuesta correcta?
Anirban Nag 'tintinmj'
9
@tintinmj Si tiene un borde saliente de D, se visitará antes de que se reduzca la distancia de D y, por lo tanto, no se actualizará después de que lo haga. Esto seguramente resultará en un error. Si considera D 2 como la distancia final ya después de escanear los bordes salientes, incluso este gráfico da como resultado un error.
Christian Schnorr
@ tb- Perdón por preguntar después de tanto tiempo pero, ¿estoy en el camino correcto aquí? Primero A->Bserá 1y A->Cserá 100. A continuación, Bse explora y se pone B->Da 2. Entonces se explora D porque actualmente tiene el camino más corto de regreso a la fuente. ¿ Estaría en lo correcto al decir que si lo B->Dfuera 100, se Chabría explorado primero? Entiendo todos los demás ejemplos que la gente da excepto el tuyo.
Pejman Poh
@PejmanPoh, según tengo entendido, si B-> D era 100, ya que A-> C es más alto en la HeapStructure que se usará, el extracto min devolverá A-> C primero, lo que significa que la siguiente ruta más corta encontrada será la ruta a C, después de eso, la ruta de C-> D que tiene un peso -5000 será la opción obvia, lo que nos llevará a la conclusión de que la ruta más corta sería de A-> C-> D y estoy bastante seguro de que esto sería ser el comportamiento normal. Entonces, a veces, cuando tenemos ciclos negativos, aún podemos obtener el valor correcto para el camino más corto, pero definitivamente no siempre, este es un ejemplo en el que no lo haremos ..
T.Dimitrov
1

Recuerde que en el algoritmo de Dijkstra, una vez que un vértice se marca como "cerrado" (y fuera del conjunto abierto), se asume que cualquier nodo que se origine en él conducirá a una mayor distancia , por lo que el algoritmo encontró el camino más corto hacia él y lo hará nunca más tendrá que desarrollar este nodo, pero esto no es cierto en caso de pesos negativos.

vineet
fuente
0

Las otras respuestas hasta ahora demuestran bastante bien por qué el algoritmo de Dijkstra no puede manejar pesos negativos en las rutas.

Pero la pregunta en sí se basa quizás en una comprensión errónea del peso de los caminos. Si se permitieran pesos negativos en las rutas en los algoritmos de búsqueda de rutas en general, obtendría bucles permanentes que no se detendrían.

Considera esto:

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

¿Cuál es la ruta óptima entre A y D?

Cualquier algoritmo de búsqueda de ruta tendría que realizar un bucle continuo entre B y C porque hacerlo reduciría el peso de la ruta total. Entonces, permitir pesos negativos para una conexión haría que cualquier algoritmo de búsqueda de ruta sea discutible, tal vez excepto si limita cada conexión para que se use solo una vez.

Dakkaron
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