En alto nivel, la forma en que funciona Dijkstra es la siguiente
Inicialice todos los vértices con distancia infinita.
1. Comience en la fuente.
2. Libere todos los bordes salientes del vértice actual (es decir, actualice el peso del vértice conectado si la nueva distancia es menor que el peso actual)
3. Tome el nodo con menos peso.
4. Repita los pasos 2 y 3 hasta que se visiten todos los vértices y ningún vértice tenga una nueva distancia actualizada.
Entonces, si hay algún ciclo negativo en el gráfico, nunca dejaría de actualizar la distancia en los vértices. Esto causará un bucle infinito. Esa es la razón por la cual Dijkstra no funciona si hay bordes negativos en el gráfico.
Nota: Hay una excepción a la regla del borde negativo. Dijkstra funciona perfectamente bien si el borde negativo está conectado al vértice de origen.
- ¿Qué algoritmos se pueden usar para determinar si dos preguntas (como las de Quora) son de alguna manera similares?
- ¿Dónde se usa el algoritmo de Dijkstra?
- ¿Es el algoritmo de búsqueda de Google realmente el mejor?
- ¿Qué estructuras de datos C ++ simples debería aprender para la programación competitiva además de un mapa?
- ¿Cuáles son los 10 algoritmos que uno debe conocer para resolver la mayoría de los problemas de algoritmos?
Editar:
Es cierto que Dijkstra no entra en bucle infinito porque nunca agregamos un vértice en el montón mínimo con la suposición básica de que el nuevo vértice siempre tendrá más peso que el anterior. Pero cuando hay un peso de borde negativo, esta suposición se anula. Aquí estoy incluyendo un ejemplo donde el algoritmo Dijkstra anterior dará un resultado incorrecto. 
Los vértices se eliminarán en el siguiente orden 
Pero la ruta más corta de A a C es A-> D -> B -> C, que es -200. Esto no se da porque no agregamos el vértice ya eliminado en el montón mínimo. Pero, ¿y si agregamos eso? Entonces el problema del bucle infinito ocurrirá en el ejemplo que ha dado. Por lo tanto, decimos que el peso de borde negativo solo se permite con la fuente porque eso siempre se procesará primero y no causará ningún problema de reducción de peso en el caso anterior.
Entonces tomemos la fuente como D. 
Aquí no hay camino de D a A, por lo tanto, A es NA.
Fuente por ejemplo:
Pesos negativos usando el algoritmo de Dijkstra
