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
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?