No busques más por internet ya que llegaste al sitio necesario, poseemos la solución que buscas sin complicarte.
Solución:
Recuerde 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 más tendrá que desarrollar este nodo, ya que asume que la ruta desarrollada a esta ruta es la más corta.
Pero con pesos negativos, puede que no sea así true. 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 numero positivo a cualquier vértice: la minimidad nunca cambiará.
Sin la restricción de números positivos, la suposición anterior no es true.
Ya que “sabemos” que cada vértice que estaba “cerrado” es mínimo – podemos hacer el paso de relajación con seguridad – sin “mirar hacia 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 el valores (la distancia desde la fuente hasta el 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 line16 el bucle no se ejecuta.
Finalmente extraemos B, después de 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 en line16,
Así que terminamos con las distancias como
Tenga en cuenta que esto es incorrecto 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 intenta encontrar una ruta más corta a los vértices que son ya extraído de Q.
Que line16 Lo que está haciendo es tomar el vértice tu y diciendo “Oye, parece que podemos ir a v desde la fuente a través de tu, ¿esa distancia (alternativa o alternativa) es mejor que la actual dist[v] ¿tenemos? Si es así, actualice dist[v]“
Tenga en cuenta que en line16 ellos revisan a todos los vecinos v (es decir, existe un borde dirigido desde u a v), de tu cuales son todavía en Q. En line14 eliminan las notas visitadas de Q. Así que si X es un vecino visitado de tu, el camino 
es 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 el camino más corto actual 
sin alterar.
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 puede ser más corta.
Entonces digo que al ejecutar este algoritmo si X se extrae de Q antes y, entonces no es posible encontrar un camino – 
que es más corto. Déjame explicarte esto con un ejemplo,
Como y acaba de ser extraído y X había sido extraído antes de sí mismo, entonces dist[y] > dist[x] porque de otra manera y habría sido extraído antes X. (line 13 distancia mínima primero)
Y como ya ficticio que los pesos de los bordes son positivos, es decir 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]. Entonces el valor de dist[x] no se habría actualizado incluso si y fue considerado como un camino hacia X, por lo que concluimos que tiene sentido considerar solo a los vecinos de y que todavía están en Q (tenga en cuenta el comentario en line16)
Pero esto depende de nuestra suposición de una longitud de borde positiva, si 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 line18.
Así que cualquiera dist[x] El cálculo que hagamos será incorrecto si X se elimina antes de todos los vértices v – tal que X es vecino de v con borde negativo que los conecta – se elimina.
Porque cada uno de esos v vértices es el penúltimo vértice en una ruta “mejor” potencial desde la fuente hasta X, que es descartado por el algoritmo de Dijkstra.
Entonces, en el ejemplo que di arriba, el error se debió a que C se eliminó antes de que se eliminara 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.