максимальный путь

[stolzen]

Имеется очень большой граф, кол-во вершин около 10^6, кол-во ребер - 10^6, Ребер раза в 1,5 больше, чем вершин, причем некоторые вершины имеют достаточно большое кол-во ребер (10, 20). В графе есть циклы.

Для поиска макс. пути можно запускать поиск в ширину из каждой вершины и смотреть, улучшился ли макс путь на этой итерации. Но это происходит ОЧЕНЬ долго. (O(n * (n + m)) = O(2 * 10^12)). За ночь работы программы ответ так и не был найден.

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

максимальный путь в графе с циклами это вообще-то бесконечность

Если максимальный путь - это самый длинный, то это np-полная задача, вряд ли её удастся решить за O(n * (n + m)).

чё ты куришь? максимальный _простой_ путь - NP-полная.

просто наидлиннейший путь - либо тривиальная динамика в ациклических графах, либо некорректно поставленная задача в графах с циклами.