Hi everyone,

I read about the SPFA a while ago and today I decided to try it out on some problems (for those who don't know about it

http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

http://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm )

Neither of the links above mentions anything about detecting negative cycles. Obviously, in the presence of a negative cycle, these implementations will never terminate. However, Steven Halim in his book says that it's sufficient to test whether a node entered the queue more than *V* - 1 times. Does anyone know a proof for this?