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

¿Alguien puede decirme por qué el algoritmo de Dijkstra para la ruta más corta de una sola fuente asume que los bordes deben ser no negativos?

Me refiero solo a los bordes, no a los ciclos de peso negativos.

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.

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.

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

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

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,

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.

Finalmente extraemos B, tras lo cual . 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,

Así que terminamos con las distancias como

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

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 está 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 no se consideró, dejando la ruta más corta actual sin 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, que 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.

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.

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.

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

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.

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.

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.