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 &lt;- 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.
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).