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

dijkstra algorithm

Question

¿Puede alguien decirme por qué el algoritmo de Dijkstra para el camino más corto de una sola fuente supone que los bordes deben ser no negativos?

Estoy hablando solamente de bordes, no de los ciclos de peso negativos.

Answer 1

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

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

Entonces, comenzar los valores ( la distancia desde la fuente hasta el vértice ) asignados inicialmente 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] . La nota A tiene un borde dirigido hacia 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 line16 ciclo de línea line16 no se ejecuta.

Finalmente extraemos B, después de lo cual . La nota B tiene un borde dirigido a C pero C no está presente en Q, por lo tanto, nuevamente no ingresamos el ciclo for en la línea line16 ,

Así que terminamos con las distancias como

Tenga en cuenta que esto es incorrecto ya que la distancia más corta desde A hasta 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 intenta encontrar una ruta más corta hacia los vértices que ya están extraídos de Q.

Lo que está haciendo el bucle de line16 es tomar el vértice y decir "parece que podemos ir a v desde la fuente a través de ti , ¿esa (alternativa o alternativa) distancia es mejor que la actual dist [v] que obtuvimos? Si es así, permite actualizar dist [v] "

Tenga en cuenta que en la línea line16 verifican todos los vecinos v (es decir, existe un borde dirigido de u a v ), de u que todavía están en Q. En la línea line14 eliminan las notas visitadas de Q. Por lo tanto, si x es un vecino visitado de usted , el camino ni siquiera se considera como un camino más corto posible de la fuente a v .

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

Entonces digo que cuando se ejecuta este algoritmo si x se extrae de Q antes de y , entonces no es posible encontrar un camino - que es más corto. Déjame explicar esto con un ejemplo,

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

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

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

Entonces, cualquier cálculo de dist [x] que hagamos será incorrecto si x se elimina antes de que todos los vértices v - tales que x sea ​​un vecino de v con flanco negativo conectándolos - se elimine.

Porque cada uno de esos vértices es el segundo último vértice en una posible "mejor" ruta de la fuente a x , que es descartada por el algoritmo de Dijkstra.

Entonces en el ejemplo que di más arriba, el error fue porque C fue removido antes de que B fuera removido. ¡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. la longitud (a, b) es la longitud del borde entre los vértices a y b.

Answer 2

El algoritmo de Dijkstra asume que las rutas solo pueden volverse más pesadas, de modo que si tienes 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 puedas agregar un borde y obtener de A a B a C con un peso de menos de 3.

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

Answer 3

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

Answer 4

Recordemos que en el algoritmo de Dijkstra, una vez que un vértice está marcado como "cerrado" (y fuera del conjunto abierto) - el algoritmo encontró el camino más corto hacia él , y nunca tendrá que desarrollar este nodo nuevamente - asume que el camino desarrollado para este el camino es el más corto

Pero con pesos negativos, podría no ser 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 desarrollará primero C, y luego no podrá encontrar A->B->C

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

Tenga en cuenta que esto es importante, porque en cada paso de relajación, el algoritmo supone que el "costo" de 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 que haga que su costo sea mínimo, al agregar cualquier número positivo a cualquier vértice, la minimización nunca cambiará.
Sin la restricción de los números positivos, la suposición anterior no es verdadera.

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

Answer 5

Corrección del algoritmo de Dijkstra:

Tenemos 2 conjuntos de vértices en cualquier paso del algoritmo. El conjunto A se compone de los vértices a los que hemos calculado las rutas más cortas. El conjunto B consiste en 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 a ser dist [V], debemos demostrar que esta distancia es óptima. Si esto no es óptimo, entonces debe haber alguna otra ruta al vértice V que sea de menor longitud.

Supongamos que esta otra ruta pasa por algún vértice X.

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

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