Здравсвуйте!
Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути? Имеется ввиду путь на графе из узла А в узел В не содержащий циклов и обладающей наибольшей стоимостью... Или какую эвристику можно применить для поиска подобного пути на большом графе (порядка N=100000 узлов, каждый узел связан с 1-4 другими, вес каждого ребра — целое число от 1 до 4 с обратным распределением (т.е. 70% ребер имеют вес 1, 20% — 2, 7% — 3, 3% — 4))??? Необходимо попадание в 10% самых длинных путей.
Заранее благодарен.
P.S. Желательно, чтобы вычислительная сложность алгоритма не превышала O(N^2)