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

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

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.

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

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?

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

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