Identify all the paths between two nodes

Users
1

Hi all,
can anyone show me a query that would find all the possible paths of maximum length between two nodes? I have seen that is possible to find the shortest so I think there might be a solution to my problem.

Thanks

1 Like
2

Hi @AlBar,

Finding the maximum length path is an NP-hard problem (except maybe directed acyclic graphs). One thing you could try is inverting the edge weights (so, 5 → -5) and then use the shortest path algorithm. Though this would only give you one path and not all the paths.

3

thanks @ashwin95r,
even condidering cyclic graphs is it possible at least if a specify the maximum length of the path)? What do you think of the following 3 solutions proposed on stack overflow?

, (http://stackoverflow.com/questions/24471136/how-to-find-all-paths-between-two-graph-nodes)

Thanks

4

Yes, if you specify the src, dest and maximum hops, we can return all the paths. We don’t have this feature yet. But if there is enough demand, we can prioritize it.

Could you please describe your use-case in brief?

1 Like
5

Thanks @ashwin95r, I’m just trying to learn graph database and I don’t have a “real” case in my head but I think in case you are developing a sat nav software. Suppose that src is where I’m at the moment dst is where I want to go and all the nodes in the between are a sort of check points.

I appreciate that you don’t have time for this feature now but, what algo would be the best for solving this problem?

Thanks

6

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.