¿Cuál es una explicación intuitiva del algoritmo de ruta más corta de Dijkstra en un gráfico con pesos negativos?

Answer 1

El algoritmo de Dijkstra no funciona correctamente en gráficos con bordes negativos.

Por lo tanto, está perfectamente bien que la metáfora con hormigas no funcione para tales gráficos.

En el algoritmo de Dijkstra, procesas vértices en el orden que corresponde a sus distancias mínimas desde la fuente. Durante la ejecución del algoritmo, hay momentos en los que declaras que la distancia a algún vértice es final, a pesar de que todavía no has visto algunos de los bordes en el gráfico. La razón por la que puede estar seguro de que la distancia es final es la suposición de que las longitudes de los bordes invisibles no son negativas.

Suponga que ejecuta el algoritmo de Dijkstra desde el vértice A. Procederá en el siguiente orden:

• La distancia final a A es 0.
• La distancia final a B es 1.
• La distancia final a C es 2.
• La distancia final a D es 9. Vaya, acabamos de mejorar el camino más corto a B a 0, a pesar de que B ya ha sido procesado. Fallar.

Si tiene un gráfico con bordes negativos pero sin ciclos negativos , aún puede usar un algoritmo diferente (por ejemplo, Bellman-Ford) para calcular las longitudes de las rutas más cortas de una sola fuente.

En gráficos con ciclos negativos, es posible que para algunos pares de vértices no haya una caminata más corta (porque siempre se puede caminar alrededor del ciclo negativo más veces), y encontrar la ruta más corta (es decir, una sin vértices repetidos) se convierte en NP- difícil.

Answer 2

¿Por qué el algoritmo de Dijkstra no funciona con borde negativo?

En la figura anterior, estamos tratando de obtener las rutas más cortas desde el nodo fuente 1 a todos los demás nodos (nodo 2 y nodo 3). Dado que el algoritmo de Dijkstra funciona empleando un proceso codicioso, genera 20 como el costo de ruta más corto para el nodo 2.

Como podemos ver, desde el nodo 1, podemos ir a dos nodos: el nodo 2 y el nodo 3, a un costo de 20 y 40 respectivamente. Por lo tanto, ir al nodo 2 es más barato. Y es por eso que genera 20 para ser el costo más barato para llegar al nodo 2.

Sin embargo, sabemos que el costo más barato para llegar al nodo 2 es a través del nodo 3. Y el costo asociado es: 40 + (-30) = 10. Entonces, el algoritmo de Dijkstra se equivoca. Se equivoca porque no puede prever que más tarde, una ventaja negativa puede reducir el costo total a menos de 20.

Si observamos cuidadosamente, vemos que el cálculo incorrecto por el algoritmo de Dijkstra ocurre debido al borde negativo. Si el costo del nodo 3 al nodo 2 no hubiera sido un valor negativo, nunca podría reducir el costo total a menos de 20, después de ser agregado a 40.

¿Por qué no agrega un costo constante a cada borde?

Ahora que nos damos cuenta, el algoritmo de Dijkstra falla debido al borde negativo del nodo 3 al nodo 2, que tiene el valor -30, podríamos sentir la tentación de agregar 30 a cada uno de los bordes. Podríamos pensar, de esta manera podemos eliminar el borde negativo. Y hacer sería justo; después de todo, estamos agregando el mismo valor a cada uno de los bordes. Hagámoslo y veamos qué pasa.

Después de actualizar los costos de borde, el gráfico se ve como se muestra arriba. Entonces, ¿cuál es la ruta más barata desde el nodo 1 al nodo 3 ahora?

Bueno, ahora el costo más barato es 50, que usa el borde directo del nodo 1 al nodo 2. Pero se supone que esta no es la ruta más barata, ¿verdad? La ruta más barata era el nodo 1 -> nodo 3 -> nodo 2 , antes de ajustar el costo del borde. El ajuste del costo del borde no debería cambiar el gráfico. No debe cambiar el camino más barato, ¿verdad?

Entonces, ¿por qué sucede eso? Bueno, si observamos, encontramos que el nodo de ruta 1 -> nodo 3 -> nodo 2 usa dos bordes / segmentos – nodo 1 al nodo 3 y nodo 3 al nodo 2. Por otro lado, ruta nodo 1 -> nodo 2 usa solo un borde / segmento. La forma en que hemos actualizado el costo de borde, agregando una constante a cada segmento de ruta, no es justo para una ruta que usa más segmentos de ruta. Para la ruta que usa dos segmentos de ruta, que originalmente era la ruta más barata, hemos agregado la constante 30 dos veces. Por otro lado, para la ruta que usa solo un segmento de ruta, hemos agregado 30 solo una vez. De esa manera, somos injustos con la ruta que utiliza más segmentos de ruta.

Debemos agregar una constante a cada una de las rutas, no a cada uno de los segmentos de ruta.

Solución

El algoritmo de Johnson hace esto: agrega un costo constante a cada ruta. Lo hace, al encontrar un conjunto especial de valores de desplazamiento para eliminar los bordes negativos de un gráfico. Una vez hecho esto, el algoritmo de Dijkstra puede funcionar. Pero eso funciona en ausencia de un ciclo negativo en el gráfico.

Esto es del problema de Dijkstra con Negative Edge en mi blog gopalcdas dot com.