2
$\begingroup$

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.

(cross posted from https://softwareengineering.stackexchange.com/questions/283038/algorithm-to-find-whether-there-is-a-path-any-path-above-length-x-between-two based on suggestions in the comments)

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't think you'll be able to find a fast algorithm. If you could decide whether there is path of length at least $k$ between two vertices $s$ and $t$ efficiently, you could solve the Hamiltonian path problem efficiently. $\endgroup$
    – Juho
    May 6, 2015 at 15:13
  • 2
    $\begingroup$ If you're interested only in simple paths, then this is probably NP-complete, since it sounds a lot like Hamiltonian path. $\endgroup$
    – Yuval Filmus
    May 6, 2015 at 15:16
  • $\begingroup$ How about using Eppstein's k-shortest paths? I read that it allows for a minimal path length, and we can have K be set to 1, will that be effective? cs.stackexchange.com/questions/18849/… $\endgroup$
    – Eran Medan
    May 6, 2015 at 17:55

1 Answer 1

Reset to default
2
$\begingroup$

If you allow duplicate vertices on your path, you can make a network from your graph by giving each edge weight $-1$. Then, use Bellman Ford to find the shortest path and see if it has length $-X$ or less.

If you don't allow repeats, then the problem is NP hard, since finding the longest simple path between two vertices tells you whether there is a Hamiltonian path or not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What I'm currently doing is using KShortestPaths (a JGraphT class that provides the K shortest paths between two vertices, ranked by distance) - what I'm currently doing is getting it (K limited to some low value to avoid running forever). And if I find any path there above length X, I return true. I wonder what is a good way to modify it, so that it will stop once it finds a path above such a length. but I guess this is more of a stackoverflow question... $\endgroup$
    – Eran Medan
    May 6, 2015 at 16:26
  • 1
    $\begingroup$ Be aware that there are an exponential number of paths, so that method will not scale unless your graphs are very sparse. $\endgroup$
    – jmite
    May 6, 2015 at 16:48

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.