algorithm - historia - algoritmos de recorrido y búsqueda el camino mas corto

Pesos negativos utilizando el algoritmo de Dijkstra

Question

Estoy tratando de entender por qué el algoritmo de Dijkstra no funciona con pesos negativos. Al leer un ejemplo en las rutas más cortas , intento 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é usando la siguiente implementación de Dijkstra, d [B] no se actualizará a 1 (Cuando el algoritmo alcance el vértice C, ejecutará un relajamiento en B, verá que d [B] es igual a 2 , y por lo tanto, actualice su valor a 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

Answer 1

"2) ¿Podemos usar el algoritmo de Dijksra para 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 a menos que todos los caminos más cortos tengan la misma longitud. Por ejemplo, dado un camino más corto de longitud dos bordes, y después de agregar valor absoluto a cada borde, entonces el costo total del camino se incrementa en 2 * | peso negativo máximo |. Por otro lado, otro camino de longitud tres aristas, por lo que el costo del camino se incrementa en 3 * | peso negativo máximo |. Por lo tanto, todos los caminos distintos se incrementan en diferentes cantidades.

Answer 2

Considera lo que sucede si vas de ida y vuelta 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 dónde va después de AC, con la suposición de que no bordes de peso negativo es imposible encontrar un camino mejor que AB una vez que elige alcanzar B después de pasar AC.

Answer 3

Dado que Dijkstra es un enfoque codicioso, una vez que se marca un vértice como visitado para este ciclo, nunca se volverá a evaluar de nuevo, incluso si hay otro camino con menor 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 lo indica, siempre toma la decisión que parece ser la mejor en ese momento. Suponga que tiene una función objetivo que necesita optimizarse (maximizada o minimizada) en un punto determinado. Un algoritmo codicioso toma decisiones codiciosas en cada paso para garantizar que la función objetivo esté optimizada. El algoritmo Greedy tiene solo una oportunidad para calcular la solución óptima para que nunca retroceda y revierte la decisión.

Answer 4

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, establece d(A) a zero y las otras distancias al infinity .
2. A continuación, expande el nodo A , estableciendo d(B) en 1 , d(C) en zero y d(D) en 99 .
3. A continuación, expandes C , sin cambios netos.
4. Luego expandes B , que no tiene efecto.
5. Finalmente, -201 D , que cambia d(B) a -201 .

Tenga en cuenta que al final de esto, sin embargo, que d(C) sigue siendo 0 , aunque el camino más corto a C tiene una longitud -200 . Por lo tanto, su algoritmo falla al calcular con precisión las distancias en algunos casos. Además, incluso si almacenara punteros retrospectivos que indicaran cómo llegar desde cada nodo al nodo inicial A , terminaría por tomar la ruta equivocada de C a A

Answer 5

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

Por supuesto, uno podría preguntar, ¿por qué en el ejemplo hecho por templatetypedef Dijkstra falla aunque no haya ciclos negativos, de hecho ni siquiera ciclos? Esto se debe a que está usando otro criterio de detención, que contiene 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 usa el criterio de parada alternativo, que detiene el algoritmo cuando la cola de prioridad (montón) se ejecuta vacía (este criterio de detención 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 previamente establecido puede reinsertarse en el montón cuando se encuentra una distancia mejor debido a los pesos negativos. Esta propiedad se llama corrección de etiquetas.

Answer 6

no usaste S en ningún lugar de tu 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 lo alcanzará nuevamente a través de 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 publicaste podría no estar en O (E + VlogV), como lo prometió el algoritmo de dijkstra.