4

We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than some X?

Should start from the shortest path, and then merge adjacent nodes if its length is less than X? (or extend the search "circle" gradually)

I don't want to first find all possible paths and then filter out those shorter than X, I want to stop the moment I find any path above a certain length between the two vertices, (and stop if I haven't found one after some MAX iterations)

(I assume I first do a shortest paths to find if there is at all any path between the nodes to avoid searching if there isn't)

It somehow feels it should be simpler that what I'm making it, but I can't seem to find a text-book algorithm for it (e.g. BFS / DFS / Dijsktra / Bellman Ford are not really helping here, right?)

I'm sure it's simple, but I need some push in the right direction.

Improve this question
7
  • This is a question that straddles domains. Please consider if you're looking for a more pragmatic answer (which you'll likely get here) or one that delves more into the theory and proof of the problem (on ComputerScience.SE). One test that I'd use for deciding which site to ask on is if you'd like an answer that uses funny greek letters or not. If you want those greek letters and formulas, please consider flagging this question for migration to CS.SE.
    – user40980
    May 6, 2015 at 2:17
  • Please leave this Q here if you repost it to comp-sci. It's a good question for this site as well as comp-sci, and you're likely to get good answers on both sites.
    – Jimmy Hoffa
    May 6, 2015 at 2:22
  • Do you allow cycles in the path? Should definitely mention that. (I presume you don't want to otherwise it's easy)
    – Jimmy Hoffa
    May 6, 2015 at 2:26
  • worst case will always be exhaustive because you don't know if there's more than one path to your target node at all. Tons of applicable heuristics though... just don't expect anything better than worst case exhaustive.
    – Jimmy Hoffa
    May 6, 2015 at 3:05
  • @JimmyHoffa - yes, no cycles in the path itself (e.g. I'm looking for a simple path, where each vertex appears in it only once, I hope I got the definition right) but it's ok if there are some paths that form cycles between those vertices. I just want to count each of the path once.
    – Eran Medan
    May 6, 2015 at 3:33

1 Answer 1

Reset to default
1

The problem you describe is the decision version of the longest path problem (ie. "Is there a path of length at least k?"). As Jimmy Hoffa noted, the problem is NP-complete. You could look into approximation algorithms for the LPP, particularly ones that exploit any special structure your graphs might have.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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