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?