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

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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – CR Drost
    Jan 21 '17 at 18:55
  • $\begingroup$ Yeah, what I meant is "minus infinity" since there are negative cycles in the graph. $\endgroup$
    – Huy Vo
    Jan 22 '17 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.