Найти самый длинный путь в графе

Question

Я пытался найти самый длинный путь в сложной сети. У меня много вопросов в StackOverflow и в Интернете, но никто не мог мне помочь. Я написал CQL как

start n=node(*) 
match p = (n)-[:LinkTo*1..]->(m) 
with n,MAX(length(p)) as L 
match p = (n)-[:LinkTo*1..]->(m) 
where length(p) = L 
return p,L 

У меня нет решения. Neo4J будет продолжать работать для ответа, и я также попытался выполнить его в Cloud-хосте Neo4J. Я даже не нашел решения, но получил ошибку «Ошибка undefined-undefined» Мне очень нужно решение. Результат для этого ответа поможет мне завершить мой проект. Поэтому, пожалуйста, помогите мне в исправлении запроса.

Answer 1

Ну, для одного вы делаете дорогостоящую операцию дважды, когда вам нужно сделать это только один раз.

Кроме того, вы возвращаете по одному пути на каждый отдельный узел в своей базе данных, по крайней мере (так как может быть несколько путей для узла, которые являются самыми длинными путями, доступными для этого узла). Но из вашего вопроса звучит так, будто вам нужен самый большой путь на графике, а не каждый для каждого отдельного узла.

Мы также можем улучшить ваше соответствие, выполнив только самое длинное совпадение на узлах, находящихся во главе пути, а не где-то посередине.

Возможно, попробуйте этот?

match (n) 
where (n)-[:LinkTo]->() and not()-[:LinkTo]->(n) 
match p = (n)-[:LinkTo*1..]->(m) 
return p, length(p) as L 
order by L desc 
limit 1 

Answer 2

Проблема, которую вы пытаетесь решить, является NP-hard. На небольших разреженных графиках подход грубой силы, такой как метод, предложенный InverseFalcon, может быть выполнен в разумные сроки, но на любом достаточно большом и/или плотно соединенном графике вы быстро столкнетесь с проблемами времени и пространства.

Если у вас есть взвешенный график, вы можете найти самый длинный путь между двумя узлами, отрицая все граничные веса и запуская алгоритм кратчайшего взвешенного пути над измененным графом. Однако, если вы хотите найти самый длинный путь на всем графике, вы эффективно пытаетесь решить Travelling Salesman Problem, но с весами -ve -ve. Вы не можете сделать это с Сайфером.

Если ваш график невзвешен, я бы нашел более легкую проблему или посмотрел, можете ли вы преобразовать свой граф в взвешенный и решить его, как описано выше. Кроме того, посмотрите, можете ли вы создать свои требования таким образом, чтобы вам не нужно находить самый длинный путь.