¿Cómo no es aplicable el algoritmo de Dijkstra a los gráficos con pesos negativos? ¿No podemos simplemente agregar alguna constante a cada peso para que cada peso sea positivo, y luego aplicar el algoritmo de Dijkstra para encontrar el camino más corto?

No puedes.
Para dar un ejemplo simple.

Sea S el vértice fuente.
Sea T el vértice de destino.
Consideramos dos rutas de S a T-ruta A y ruta B.
Camino A
S -1-> X-1-> Y – (- 3) -> T
aquí los pesos de borde son
SX = 1
XY = 1
y YT = -3
Camino b
S -1-> T
aquí los pesos de borde son
ST = 1

Ahora digamos que agrega x a cada peso de borde.
Entonces, para la ruta A, agrega un total de 3x peso y para la ruta B agrega un total de x peso.

Dado que, en el caso original PathA cual es
(1 + x) + (1 + x) + (- 3 + x) <1 + x
resolviendo lo que obtienes
x <1
Esto significa que para cualquier x> = 1 , el invariante no se mantendría.
Pero, x <1 significa que el borde YT = -3 + x siempre permanecerá negativo.

Por lo tanto, incluso después de agregar los pesos positivos que satisfacen a los invariantes, YT sigue siendo negativo. Si elige cualquier otro peso positivo, cambia el gráfico por completo.

El algoritmo de Dijkstra no puede funcionar con borde negativo. Además, no podemos agregar trivialmente una constante a cada uno de los pesos de los bordes y hacer que no sean negativos para continuar.

¿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 alcanzar el 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 hacerlo 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 la ruta nodo 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 con una determinada fuente s a un determinado objetivo t. 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 de mi publicación El problema de Dijkstra con borde negativo en mi blog Compartiendo experiencias ( gopalcdas dot com ).

Los pesos negativos del borde, prácticamente, no tienen sentido. Por ejemplo, si la suma de todos los bordes en un ciclo en un gráfico es negativa, puede pasar por ese ciclo una y otra vez para reducir el costo. Este ciclo nunca terminará porque cada vez que se reduce su costo. Entonces, la primera suposición implica que los pesos de borde son positivos.

Agregar un valor constante a todos los bordes lo convertiría en un problema diferente porque si hay caminos con diferente número de bordes y agregamos un valor constante a cada borde, entonces un borde se incrementaría en una cantidad mayor (el que tiene más bordes) y esto no dará como resultado una solución óptima.