Inteligencia Artificial - Duda con algoritmo de Dijkstra

¿Qué ocurre cuando el algoritmo de Dijkstra se le proporciona un grafo de pesos negativos?

Hasta donde sé este algoritmo solo puede ser utilizado con arboles de pesos positivos, al utilizarlo de esta forma, que es lo que sucede.

saludos

En teoria el algoritmo deberia funcionar de la misma manera, una vez que un nodo pierde su infinito, que siempre y cuando este coenctado al nodo con el que quieres trabajar lo va hacer, todo se convierte en sumas que convergen a un resultado. La duda mas bien estaria en como interpretar un valor negativo para el costo de un arco en un grafo?