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