Как нужно изменить алгоритм Дейкстры чтобы он искал самый длинный путь?
Варианты.
1. Если граф циклический, максимальный путь — ∞.
2. Если циклический, но путь обязан быть несамопересекающимся — Дейкстра не подойдёт. Подобную олимпиадную задачу я решал и там решением был перебор с кэшированием (вершин вроде до 15).
3. Если граф циклический, но есть отрицательные веса, которые в определённых случаях дают-таки точный максимум — меняем знак, применяем модификацию Дейкстры для отрицательных весов. Он либо скажет, что есть цикл, позволяющий сколь угодно уменьшить сумму, либо даст точный минимум.
4. Если ациклический ненаправленный — то либо один, либо нет вообще (т.н. лес);
5. Если ациклический направленный — должен работать совсем другой алгоритм: отсортировать в топологическом порядке, убрать те элементы, которые перед началом и за концом, а на оставшихся пустить динамическое программирование.
Никак, максимальный путь - бесконечность.