# Bellman-Ford: Find all nodes that have minus infinite distance to source

Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node u, if there is a path from s to u but there is no shortest path from s to u (the distance from s to u is minus infinite). To do this I implemented a version of the Bellman-Ford algorithm:

Do V iterations of Bellman-Ford, save all nodes relaxed on Vth iteration to a queue Q
Do BFS with Q and find all nodes reachable from Q
All those nodes and only those can have infinite distance from s


Here is BFS:

visited(Q.first) = true
while Q not empty:
u <- Q.deQueue()
shortest[u] = 0 // there is no shortest path from s to u
for all (u, v) in E:
if not visited(v):
visited(v) = true
Q.push(v)


This algorithm is the best I can come up with and sadly it fails some test cases. I would be greatly appreciated if you guys can help, thanks.

• When you say "is infinite," just to clarify, you mean "is minus infinity," yes? Otherwise, how are you modelling "a path exists but its sum-of-weights is infinite", what sort of situation provokes that? Commented Jan 21, 2017 at 18:55
• Yeah, what I meant is "minus infinity" since there are negative cycles in the graph. Commented Jan 22, 2017 at 2:14

Well after a morning of testing, I just figured out that my solution is RIGHT, the problem I had before is because of overflow (I use 10^19 to declare infinity for all vertices at the beginning and it can leads to overflow for some test cases).